动态规划算法专题（四）：子串、子数组系列

1、最大子数组和

1.1 算法原理

1.2 算法代码

2、环形子数组的最大和

2.1 算法原理

2.2 算法代码

3、乘积最大子数组

3.1 算法原理

3.2 算法代码

4、乘积为正数的最长子数组长度

4.1 算法原理

4.2 算法代码

5、等差数列划分

5.1 算法原理

5.2 算法代码

6、最长湍流子数组

6.1 算法原理

6.2 算法代码

7、单词拆分

7.1 算法原理

7.2 算法代码

8、环绕字符串中唯一的子字符串

8.1 算法原理

8.2 算法代码

1、最大子数组和

. - 力扣（LeetCode）

1.1 算法原理

状态表示dp[i]：

以i位置为结尾，最长子序列之和

状态转移方程：

dp[i]=max(dp[i-1]+nums[i-1],nums[i-1]);

初始化：

int[] dp = new int[n+1];
dp[0]=0;

填表顺序：

从左往右

返回值：

dp中最大序列和

1.2 算法代码

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];// 初始化dp[0] = 0;int ret = Integer.MIN_VALUE;// 填表for(int i = 1; i <= n; i++) {dp[i] = Math.max(dp[i - 1] + nums[i - 1], nums[i - 1]);ret = Math.max(ret, dp[i]);}return ret;}
}

2、环形子数组的最大和

. - 力扣（LeetCode）

2.1 算法原理

核心：将带环问题转化为普通不带环问题

状态表示：

f[i]：以i位置为结尾，最大子序列之和
g[i]：以i位置为结尾，最小子序列之和

状态转移方程：

f[i] = Math.max(f[i - 1] + nums[i - 1], nums[i - 1]);

g[i] = Math.min(g[i - 1] + nums[i - 1], nums[i - 1]);

初始化：

下标映射：dp[i]-->nums[i-1]
虚拟节点：要保证后续填表的正确性：f[0]=g[0]=0;

填表顺序：

从左往右，两个表一起填。

返回值(特殊情况：当表中的数都是负数时(都在最小子序列中)，此时sum-gMin=0)：

找到f表中的最大值 fMax;
找到g表中的最小值 gMin，进而得到最大和序列：sum-gMin；
return sum == gMin ? fMax : max(fMax, sum-gMin);

2.2 算法代码

class Solution {public int maxSubarraySumCircular(int[] nums) {int n = nums.length;int sum = 0;for(int x : nums) sum += x;int[] f = new int[n + 1];//内部最大子数组int[] g = new int[n + 1];//内部最小子数组f[0] = g[0] = 0;int fMax = Integer.MIN_VALUE;int gMin = Integer.MAX_VALUE;for(int i = 1; i <= n; i++) {f[i] = Math.max(f[i - 1] + nums[i - 1], nums[i - 1]);g[i] = Math.min(g[i - 1] + nums[i - 1], nums[i - 1]);fMax = Math.max(fMax, f[i]);gMin = Math.min(gMin, g[i]);}// 注意数组中全是负数的情况return sum == gMin ? fMax : Math.max(fMax, sum - gMin);}
}

3、乘积最大子数组

. - 力扣（LeetCode）

3.1 算法原理

状态表示：

f[i]：以i位置为结尾，最大乘积
g[i]：以i位置为结尾，最小乘积

状态转移方程：

f[i]=max(nums[i-1], f[i-1]*nums[i-1], g[i-1]*nums[i-1]);
g[i]=min(nums[i-1], f[i-1]*nums[i-1], g[i-1]*nums[i-1])；

初始化：

f[1]=g[1]=1;

建表顺序：

从左往右，两个表一起填

返回值：

f表中的最大值

3.2 算法代码

class Solution2 {public int maxProduct(int[] nums) {int n = nums.length;int[] f = new int[n + 1];// 以i位置为结尾，最大乘积int[] g = new int[n + 1];// 以i位置为结尾，最小乘积int ret = Integer.MIN_VALUE;// 初始化f[0] = g[0] = 1;// 建表for(int i = 1; i <= n; i++) {f[i] = Math.max(nums[i - 1], Math.max(nums[i - 1] * f[i - 1], nums[i - 1] * g[i - 1]));g[i] = Math.min(nums[i - 1], Math.min(nums[i - 1] * f[i - 1], nums[i - 1] * g[i - 1]));ret = Math.max(ret, f[i]);}return ret;}
}

4、乘积为正数的最长子数组长度

. - 力扣（LeetCode）

4.1 算法原理

状态表示：

f[i]：以i位置为结尾，乘积为正数的，最长子序列的长度。

g[i]：以i位置为结尾，乘积为负数的，最长子序列的长度。

状态转移方程：

①：nums[i] > 0

f[i] = f[i-1]+1; g[i] = (g[i-1]==0 ? 0 : g[i-1]+1);

②：nums[i] < 0

f[i] = (g[i-1]==0 ? 0 : g[i-1]+1); g[i] = f[i-1]+1;

初始化：

①：f[0]=g[0]=0; // 虚拟节点的值，不影响后续填表的正确性

②：下标映射关系

返回值：

f表中的最大值

4.2 算法代码

class Solution {public int getMaxLen(int[] nums) {int n = nums.length;int[] f = new int[n + 1];// 乘积为正数的最长序列的长度int[] g = new int[n + 1];// 乘积为负数的最长序列的长度int ret = 0;// 填表for(int i = 1; i <= n; i++) {if(nums[i - 1] > 0) {f[i] = f[i - 1] + 1;g[i] = (g[i - 1] == 0 ? 0 : g[i - 1] + 1);}if(nums[i - 1] < 0) {f[i] = (g[i - 1] == 0 ? 0 : g[i - 1] + 1);g[i] = f[i - 1] + 1;}ret = Math.max(ret, f[i]);}return ret;}
}

5、等差数列划分

. - 力扣（LeetCode）

5.1 算法原理

状态表示dp[i]：

以i位置为结尾的所有子序列中，等差序列(长度>=3)的数量

状态转移方程：

①：nums[i]-nums[i-1] == nums[i-1]-nums[i-2] => dp[i]=dp[i-1]+1;

②：nums[i]-nums[i-1] != nums[i-1]-nums[i-2] => dp[i]=0;

初始化：

dp[0]=dp[1]=0;(子序列长度不足3)

返回值：

dp表之和

5.2 算法代码

class Solution {public int numberOfArithmeticSlices(int[] nums) {int n = nums.length;int[] dp = new int[n];int ret = 0;// 填表for(int i = 2; i < n; i++) {if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {dp[i] = dp[i - 1] + 1;ret += dp[i];}}return ret;}
}

6、最长湍流子数组

. - 力扣（LeetCode）

6.1 算法原理

状态表示：

f[i]：以i位置为结尾，最后呈现"上升趋势"的最长子序列的长度
g[i]：以i位置为结尾，最后呈现"下降趋势"的最长子序列的长度

状态转移方程：

if(nums[i] > nums[i-1]) f[i]=g[i-1]+1;
if((nums[i] < nums[i-1]) g[i]=f[i-1]+1;

初始化：

f表，g表中所有元素的值初始化为 1
(最差情况序列长度为1)

建表顺序：

从左往右

返回值：

f 和 g 表中的最大值

6.2 算法代码

class Solution {public int maxTurbulenceSize(int[] arr) {int n = arr.length;int[] f = new int[n];// f[i]: 最后呈现"上升"趋势的最长湍流子数组的长度int[] g = new int[n];// g[i]: 最后呈现"下降"趋势的最长湍流子数组的长度// 初始化Arrays.fill(f, 1);Arrays.fill(g, 1);int ret = 1;// 建表 + 处理返回值for(int i = 1; i < n; i++) {if(arr[i] > arr[i - 1]) f[i] = g[i - 1] + 1;if(arr[i] < arr[i - 1]) g[i] = f[i - 1] + 1;ret = Math.max(ret, Math.max(f[i], g[i]));}return ret;}
}

7、单词拆分

. - 力扣（LeetCode）

7.1 算法原理

状态表示dp[i]：

[0, i]区间的字符串，能否被字典中的单词拼接而成

状态转移方程：

根据最后一个单词的位置，划分问题。
设j为最后一个单词的起始位置(0<=j<=i)，
判断条件①：[j, i]区间的字符串是否存在于字典中
判断条件②：[0, j-1]区间的字符串是否可被拼接而成

初始化：

dp[0]=true;(里面的值要保证后续的填表是正确的)
优化：s = s+ " ";(下标映射的处理)

填表顺序：

从左往右

返回值：

dp[n];

7.2 算法代码

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 优化一：哈希Set<String> hash = new HashSet<>(wordDict);int n = s.length();boolean[] dp = new boolean[n + 1];s = " " + s;// 初始化dp[0] = true;for(int i = 1; i <= n; i++) {for(int j = i; j >= 1; j--) {if(hash.contains(s.substring(j, i + 1)) && dp[j - 1]) {dp[i] = true;// 优化二break;}}}return dp[n];}
}

8、环绕字符串中唯一的子字符串

. - 力扣（LeetCode）

8.1 算法原理

状态表示：

以i位置字符为结尾的所有不同的子串，有多少个在base中出现过

状态转移方程：

if(s[i-1]+1 == s[i] || (s[i-1] == 'z' && s[i] == 'a')) --> dp[i] += dp[i-1];

初始化：

Arrays.fill(dp, 1);// 最差情况下，字符本身构成base中的子串

填表顺序：

从左往右

返回值：

给重复的子串去重：
相同字符结尾的dp值，取最大的即可(虽然是相同字符结尾的子串，但dp值更大的这种情况，
包含了dp值小的情况)：
1. int[26] hash // 存相应字符结尾的最大的dp值
2. 返回hash数组的和

8.2 算法代码

class Solution {public int findSubstringInWraproundString(String ss) {char[] s = ss.toCharArray();int n = s.length;// 状态表示：以i位置字符为结尾的所有不同的子串，有多少个在base中出现过int[] dp = new int[n];int[] hash = new int[26];Arrays.fill(dp, 1);// 填表for(int i = 1; i < n; i++) {if(s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a')) {dp[i] += dp[i - 1];}}// 去重for(int i = 0; i < n; i++) {int index = s[i] - 'a';hash[index] = Math.max(hash[index], dp[i]);}// 返回结果int ret = 0;for(int x : hash) ret += x;return ret; }
}

END