子数组问题最大子数组和环形子数组的最大和乘积最大的子数组乘积为正数的最长子数组长度等差数列划分单词拆分环绕字符串中唯一的子字符串最大子数组和题目解析找出数组中和最大的子数组并返回最大和动态规划状态表示dp[i]表示以i位置为结尾的最大子数组和状态转移方程dp[i] Math.max(nums[i ], dp[i - 1] nums[i ]);初始化dp[0] 0 或者引入一个虚拟位置dp从1下标开始填表顺序从左到右返回值dp表中的最大值classSolution{publicintmaxSubArray(int[]nums){intnnums.length;int[]dpnewint[n1];dp[0]0;intret-Integer.MIN_VALUE;for(inti1;in;i){dp[i]Math.max(nums[i-1],dp[i-1]nums[i-1]);retMath.max(ret,dp[i]);}returnret;}}环形子数组的最大和题目解析找出数组中的连续子数组的最大和并返回最大和数组是环形(首尾相连)将其分为两种情况1和上题不是环形的一样正常找出的连续子数组的最大和2.利用了环形性质找出连续子数组的最小和sum-min就是其对应最大和动态规划状态表示f[i]表示以i位置为结尾的最大子数组和g[i]表示以i位置为结尾的最小子数组和状态转移方程f[i] Math.max(nums[i ], f[i - 1] nums[i ]);g[i] Math.max(nums[i ], g[i - 1] nums[i ]);初始化f[0] g[0] nums[0]或者引入虚拟节点f[0] g[0] 0,此时与nums数组下标对应关系有所改变填表顺序从左到右返回值Math.max(fmax,sum - gmin)//不使用虚拟节点classSolution{publicintmaxSubarraySumCircular(int[]nums){intnnums.length;intsum0;intfmaxInteger.MIN_VALUE;intgminInteger.MAX_VALUE;int[]fnewint[n];//最大值int[]gnewint[n];//最小值//初始化f[0]g[0]nums[0];sumnums[0];fmaxMath.max(fmax,f[0]);gminMath.min(gmin,g[0]);for(inti1;in;i){f[i]Math.max(nums[i],f[i-1]nums[i]);g[i]Math.min(nums[i],g[i-1]nums[i]);sumnums[i];fmaxMath.max(fmax,f[i]);gminMath.min(gmin,g[i]);}//可能数组全是负数这样直接返回fmax即可returngminsum?fmax:Math.max(fmax,sum-gmin);}}classSolution{publicintmaxSubarraySumCircular(int[]nums){intnnums.length;intsum0;intfmaxInteger.MIN_VALUE;intgminInteger.MAX_VALUE;int[]fnewint[n1];//最大值int[]gnewint[n1];//最小值for(inti1;in;i){f[i]Math.max(nums[i-1],f[i-1]nums[i-1]);g[i]Math.min(nums[i-1],g[i-1]nums[i-1]);sumnums[i-1];fmaxMath.max(fmax,f[i]);gminMath.min(gmin,g[i]);}//可能数组全是负数这样直接返回fmax即可returngminsum?fmax:Math.max(fmax,sum-gmin);}}乘积最大的子数组题目解析找出数组中最大连续子数组积数组中是有负数的使用一个dp表表示以i位置为结尾的最大子数组积是不够的因为负负得正当前数是一个负数从前面找一个最小的子数组积此时才是最大的动态规划状态表示f[i]表示以i位置为结尾的最大连续子数组积g[i]表示以i位置为结尾的最小连续子数组积状态转移方程f[i] max(nums[i] , f[i-1] * nums[i] , g[i-1] * nums[i])g[i] min(nums[i] , f[i-1] * nums[i] , g[i-1] * nums[i])初始化引入虚拟节点f[0] g[0] 1,此时与nums数组下标对应关系有所改变填表顺序从左到右返回值f表中的最大值classSolution{publicintmaxProduct(int[]nums){intnnums.length;int[]fnewint[n1];int[]gnewint[n1];f[0]g[0]1;intretInteger.MIN_VALUE;for(inti1;in;i){intxnums[i-1];intyf[i-1]*nums[i-1];intzg[i-1]*nums[i-1];f[i]Math.max(Math.max(x,y),z);g[i]Math.min(Math.min(x,y),z);retMath.max(f[i],ret);}returnret;}}乘积为正数的最长子数组长度题目解析乘积为正的连续子数组最长长度动态规划状态表示f[i]表示以i位置为结尾的乘积为正的最长子数组长度g[i]表示以i位置为结尾的乘积为负的最长子数组长度状态转移方程nums[i] 0f[i] f[i-1] 1; g[i] g[i-1] 0 ? 0 : g[i-1] 1;nums[i] 0f[i] g[i-1] 0 ? 0 : g[i-1] 1; g[i] f[i-1] 1;初始化引入虚拟节点f[0] g[0] 1,此时与nums数组下标对应关系有所改变填表顺序从左到右返回值f表中的最大值classSolution{publicintgetMaxLen(int[]nums){intnnums.length;int[]fnewint[n1];int[]gnewint[n1];intretInteger.MIN_VALUE;for(inti1;in;i){if(nums[i-1]0){f[i]f[i-1]1;g[i]g[i-1]0?0:g[i-1]1;}elseif(nums[i-1]0){f[i]g[i-1]0?0:g[i-1]1;g[i]f[i-1]1;}retMath.max(ret,f[i]);}returnret;}}等差数列划分题目解析求出一个数组中连续子数组可以构成等差数列的个数动态规划状态表示dp[i]以i位置结尾的连续子数组为等差数列的个数状态转移方程dp[i] nums[i] - nums[i-1] nums[i-1] - nums[i-2] ? dp[i-1] 1 : 0;初始化dp[0] dp[1] 0填表顺序从左到右返回值f表中总和classSolution{publicintnumberOfArithmeticSlices(int[]nums){intret0;intnnums.length;int[]dpnewint[n];for(inti2;in;i){dp[i]nums[i]-nums[i-1]nums[i-1]-nums[i-2]?dp[i-1]1:0;retdp[i];}returnret;}}题目解析求连续湍流子数组的最长长度动态规划状态表示f[i]表示以i位置为结尾的最后呈现上升趋势最长湍流子数组长度g[i]表示以i位置为结尾的最后呈现下降趋势最长湍流子数组长度状态转移方程f[i] g[i] 1if (arr[i] arr[i - 1]) {f[i] g[i - 1] 1;} else if (arr[i] arr[i - 1]) {g[i] f[i - 1] 1;}初始化可以将所有f表和g表全部初始为1填表顺序从左到右返回值f和g表中最大值classSolution{publicintmaxTurbulenceSize(int[]arr){intnarr.length;int[]fnewint[n];int[]gnewint[n];//因为这里最小是1可以将f表和g表全部初始化为1for(inti0;in;i){f[i]g[i]1;}intret1;for(inti1;in;i){if(arr[i]arr[i-1]){f[i]g[i-1]1;}elseif(arr[i]arr[i-1]){g[i]f[i-1]1;}retMath.max(Math.max(f[i],g[i]),ret);}returnret;}}//不将其全部初始为1//进入循环可以先将其初始化为1符合湍流条件进行更新classSolution{publicintmaxTurbulenceSize(int[]arr){intnarr.length;int[]fnewint[n];int[]gnewint[n];intret1;f[0]g[0]1;for(inti1;in;i){//不符合表的特征为1f[i]g[i]1;if(arr[i]arr[i-1]){f[i]g[i-1]1;}elseif(arr[i]arr[i-1]){g[i]f[i-1]1;}retMath.max(Math.max(f[i],g[i]),ret);}returnret;}}单词拆分题目解析给一个s字符串和一个字典判断利用字典中的单词是否可以拼接处s这个字符串(字典中单词可以重复使用)动态规划状态表示布尔类型dp[i]s字符串[0,i]区间是否可以使用字典中单词拼接而成状态转移方程判断[0,i]区间字符串是否可以被拼接而成可以将其分为两部分[0,j-1]和[j,i]j的取值范围[0,i]条件1 [0,j-1] - dp[j-1]条件2[j,i] - 判断s字符串中是否存在这个单词当条件1和2都满足此时dp[i]是true如果所有情况都不满足返回false初始化引入一个虚拟节点 dp[0] true填表顺序从左到右返回值dp[i]细节优化 优化1可以使用一个哈希表将字典中单词放入方便查找一个单词是否在字典中 优化2dp表引入了虚拟节点下标对应关系和s字符串有所改变 可以让s s将字符串s向后移动一个位置,这样下标就一一对应classSolution{publicbooleanwordBreak(Strings,ListStringwordDict){SetStringhashnewHashSet(wordDict);intns.length();boolean[]dpnewboolean[n1];s s;//方便处理下标映射关系dp[0]true;for(inti1;in;i){for(intji;j1;j--){//[1,j-1] - dp[j-1]为true// [j,i]存在字典中if(dp[j-1]hash.contains(s.substring(j,i1))){dp[i]true;break;}}}returndp[n];}}环绕字符串中唯一的子字符串题目解析有一个base字符串其是abcdef…………xyzabce……26个小写字母无限环绕的字符串给了一个字符串s,求s中有多少不同的子串在base出现动态规划状态表示dp[i] : 以i位置的元素结尾的有多少子串存在base中状态转移方程dp[i]的值为以i元素结尾子串长度为1 子串长度1之和dp[i] 1 dp[i-1]前提是s[i-1] 和 s[i]是连续的初始化可以将dp表中都现初始化为1因为其长度为1都是在base中的此时这里状态转移方程变成 dp[i] dp[i-1]满足条件才进行相加填表顺序从左到右返回值不可以直接返回dp表所有值之和因为有重复因为以同一字符结尾dp值肯定更长的dp值更大并且其是包含相同结尾较短字符中的所有情况所以此时直接返回所有字符结尾中dp表中最大值此时可以使用一个26数组统计对应以某个字符结尾的最大结果即可classSolution{publicintfindSubstringInWraproundString(Stringss){char[]sss.toCharArray();intnss.length();int[]hashnewint[26];//以这个字符结尾有多少子串在环绕字符串中int[]dpnewint[n];//此时这里都是由小写字母组成单个字符肯定符合for(inti0;in;i){dp[i]1;}hash[s[0]-a]1;for(inti1;in;i){if(s[i-1]1s[i]||(s[i-1]zs[i]a)){dp[i]dp[i-1];}//更新哈希表(去重)hash[s[i]-a]Math.max(dp[i],hash[s[i]-a]);}intret0;for(inti0;i26;i){rethash[i];}returnret;}}