【动态规划】子数组系列（上）

1. 最大子数组和

53. 最大子数组和

状态表示：以 i 位置为结尾时的所有子数组中的最大和

状态转移方程：

i 位置为结尾的子数组又可以分为长度为 1 的和大于 1 的，长度为 1 就是 nums[i] ，长度不为 1 就是 dp[i - 1] + nums[i]，最后取这两个的最大值即可

初始化：可以多开一个元素，为了不影响后续的值默认为 0 即可，也可以单独对 dp[0] 进行初始化，就不用多开一个元素了

填表顺序：从左到右

返回值：整个 dp 表中的最大值，因为结果可能是以任意位置结尾的，如果多开一个元素的话最后取最大值就不能再带上这个值了

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];//dp[0] = Math.max(0,nums[0]);int res = -0x3f3f3f;for(int i = 1;i <= n;i++){dp[i] = Math.max(nums[i - 1],dp[i - 1] + nums[i - 1]); res = Math.max(res,dp[i]);}return res;}
}

2. 环形子数组的最大和

918. 环形子数组的最大和

这道题和上道题不同的就是是一个环形结构，首尾可以相连，这就会有下面两种情况

情况一和上一题是一样的，就是正常的求最大的子序列和，情况二就是首尾相连的情况，可以转化为求中间部分最小的子序列和，再用总的数组和减去这部分最小的子序列和就是最大子序列和，这两种情况求最大值就可以了

状态表示和状态转移方程都和上一题是类似的

初始化：求最大子序列和时还是 dp[0] 初始化为 0，不过求最小子序列就不一样了

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

求 dp[1] 时需要让最后的结果等于 num[0]，所以 dp[i - 1] 就需要设为 0 或者一个很大的数，不过不能设为 int 的最大值，不然可能会溢出

返回值：返回两种情况的最大值，不过有一种情况需要注意，当数组中全是负数的话，第一种情况求的就是负数，第二种情况求的最小值就是整个数组和，再用数组和减去这个最小值就是 0 ，代表什么都不选，肯定是比第一种情况大的，这个时候还是需要返回第一种情况的值

class Solution {public int maxSubarraySumCircular(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];int ret1 = Integer.MIN_VALUE;int sum = 0;for(int i = 1;i <= n;i++){dp[i] = Math.max(nums[i - 1],dp[i - 1] + nums[i - 1]);ret1 = Math.max(ret1,dp[i]);sum += nums[i - 1];}int ret2 = Integer.MAX_VALUE;dp[0] = 0x3f3f3f;for(int i = 1;i <= n;i++){dp[i] = Math.min(nums[i - 1],dp[i - 1] + nums[i - 1]);ret2 = Math.min(ret2,dp[i]);}if(sum == ret2) return ret1;return Math.max(ret1,sum - ret2);}
}

3. 乘积最大子数组

152. 乘积最大子数组

这道题求的是乘积最大的子数组，由于是乘法，就意味着两个负数乘完之后也会变成整数

状态表示：先定义为以 i 位置为结尾时的所有子数组中的最大乘积发现，如果是负数的话也可以乘进来，所以可以定义两个状态

以 i 位置为结尾时的所有子数组中的最大乘积

以 i 位置为结尾时的所有子数组中的最小乘积

状态转移方程：

求 f[i] 时，如果说当前元素是一个负数，那么就需要乘上一个最小的负数，也就是 g[i - 1]，如果是正数的话正常求前一个状态的最大值再乘当前元素就行，最终确定最大值时需要再加上当前元素，这三个数一起求一个最大值即可

同理，求最小值 g[i] 时，如果说当前元素是一个正数，那么就需要乘上一个最小的负数，也就是 g[i - 1]，如果是负数的话就需要找一个最大的正数来乘，最终确定最小值时需要再加上当前元素，这三个数一起求一个最小值即可

初始化：把 f[0] 和 g[0] 设置为 1 就不影响后续的乘积赋值

填表顺序：从左到右

返回值：f 表中的最大值

class Solution {public int maxProduct(int[] nums) {int n = nums.length;int[] f = new int[n + 1];int[] g = new int[n + 1];f[0] = 1;g[0] = 1;int ret = Integer.MIN_VALUE;for(int i = 1;i <= n;i++ ){f[i] = Math.max(Math.max(nums[i - 1], f[i - 1] * nums[i - 1]), g[i - 1] * nums[i - 1]);g[i] = Math.min(Math.min(nums[i - 1], f[i - 1] * nums[i - 1]), g[i - 1] * nums[i - 1]);ret = Math.max(ret,f[i]);}return ret;}
}

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

1567. 乘积为正数的最长子数组长度

状态表示：

f[i]：以 i 位置为结尾的所有子数组中乘积为正数的最长长度

g[i]：以 i 位置为结尾的所有子数组中乘积为负数的最长长度

状态转移方程：

还是和之前一样，可以分为长度为 1 的和长度大于 1 的，当长度为 1 时又可以分为 nums[i] 是正数还是负数两种情况，当是正数时长度就是 1，负数时就是 0，再看长度大于 1 的，也可以分为 nums[i] 是正数还是负数两种情况，当 num[i] 是正数时，就是从以 i - 1 为结尾时数组中的乘积为正数的最长长度加 1 即可，也就是 f[i - 1] + 1，当 num[i] 是负数时，就需要在 i - 1 为结尾时数组中的乘积为负数的长度加上 1，所以需要再定义一个 g[i] 状态数组来表示，也就是 g[i - 1] + 1，但是如果之前找不到一个以 i - 1 为结尾的数组，那么 g[i - 1] 就是 0，此时就不能继续加 1，因为 num[i] 是负数，这个长度不能加

为了简便，长度为 1 时的状态可以和下面长度大于 1 的合并一下，不影响结果

接下来看 g[i] 的状态转移方程：同理，也可以分为长度为 1 和长度大于 1 两种情况，接着二者又可以分为 num[i] 大于 0 和小于 0 两种情况，当 num[i] 大于 0 时，需要找到 i - 1 为结尾的乘积为负数的最长长度，也就是 g[i - 1]，然后加 1，这里还是一样的，如果没有找到，那么 g[i - 1] 就是 0，num[i] 为正数，要求的是负数，所以这个 1 需要判断一下才能加，num[i] 小于 0 时，就需要找一个 i - 1 为结尾的乘积为正数的最长长度，也就是 f[i - 1] 再加 1，这时就不需要判断，找不到也没关系，可以直接 + 1

长度为 1 时也可以合并一下，不影响结果

nums[i] 等于 0 的情况直接不考虑就行

初始化：如果 nums[0] 是大于 0 的话，g[1] 应该是 0，也就是 g[0] = 0即可， 如果是小于 0 的话 g[1] 应该是 1，也就是 f[0] 应该是 0

填表顺序：从左到右，两个表一起填

返回值：f 表中的最大值

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;}else 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(f[i],ret);}return ret;}
}