动态规划-子数组1

---

1. 最大子数组和（53）

题目描述：

状态表示：
根据经验以及题目要求设置数组dp[i]表示以i位置为结尾的最大子数组和。
状态转移方程：
第i个数组元素可以单独构成子数组也可以和前面的i-1或者和i-1、i-2构成子数组，第i个元素单独构成子数组为dp[i]=num[i]，第i个元素和前面元素构成子数组，即dp[i]=dp[i-1]+nums[i],所以最终的dp[i]=max(dp[i-1]+nums[i],nums[i])。
初始化：
为了避免数组越界，初始化dp[0]=nums[0]。
填表顺序：
从左至右。
返回值：
返回dp数组中的最大值。
代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n];
        dp[0] = nums[0];

        int max = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

题目链接
时间复杂度:O(n)
空间复杂度:O(n)

2. 环形子数组的最大和（918）

题目描述：
**
状态表示：
这题的状态表示方法和上一题是类似的，但是做法与上一题不同，因为这里涉及到环形数组的最大子数组和相当于数组的前后是相连的。环形数组的最大子数组和有两种情况，如下图。所以这里需要将两种情况的最大值都求出来然后返回两者中的最大值，第一种情况很简单就是上一题的求法定义f[i]表示以i位置为结尾的最大子数组和。第二种情况可以先求出在第一种情况的最小子数组和，然后将总的数组和减去最小数组和即可得到，g[i]表示以i位置为结尾的最小子数组和。

状态转移方程：
f[i]=max(f[i-1]+nums[i],nums[i])和g[i]=max(g[i-1]+nums[i],nums[i])。

初始化：
nums数组长度为n，为了方便初始化可以将f和g的长度设为n+1,然后初始化f[0]和g[0]的值。这里的初始化的值不能够影响最终输出的结果。如果f和g数组按正常步骤设为长度为n的数组，那么f[0]和g[0]应该都等于nums[0]。如果f和g设为n+1长度的数组，f[0]和g[0]变为f[1]和g[1]，为了使f[0]和g[0]不影响f[1]和g[1]的nums[0]的值，根据状态转移方程，f[0]和g[0]应该赋为0。还要一个细节当f和g都设为n+1长度后要注意和nums数组的映射关系。
填表顺序：
从左至右。
返回值：
返回f数组的最大值和总数组和减去g数组最小值之间的最大值，这里注意一个细节当数组全为负数时，总数组和减去g数组最小值为0那么代码就会返回0，但是数组中全是负数。因此当发生这种情况时就直接返回f数组的最大值。
代码如下：

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }

        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        int max = Integer.MIN_VALUE;
        int min = 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]);
            max = Math.max(max, f[i]);
            min = Math.min(min, g[i]);
        }

        return sum == min ? max : Math.max(max, sum - min);

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

题目链接
时间复杂度:O(n)
空间复杂度:O(n)

3. 乘积最大子数组（152）

题目描述：

状态表示：
设置两个数组分别为f[i]和g[i]分别代表以i位置为结尾的子数组最大乘积和最小乘积。
状态转移方程：
当nums[i]大于0时，f[i]=max(f[i-1]*nums[i],nums[i]),g[i]=min(g[i-1]*nums[i],nums[i])。当nums[i]小于0时，f[i]=max
(g[i-1]*nums[i],nums[i]),g[i]=min(f[i-1]*nums[i],nums[i])。
初始化：
初始化为了避免越界以及方便运算，将f和g的长度设为n+1，f[0]和g[0]都初始化为1，这样不会影响最终的输出结果，还有一个细节就是要注意nums数组的下标映射。
填表顺序：
从左至右。
返回值：
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 max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] < 0) {
                f[i] = Math.max(g[i - 1] * nums[i - 1], nums[i - 1]);
                g[i] = Math.min(nums[i - 1], f[i - 1] * nums[i - 1]);
            } else {
                f[i] = Math.max(f[i - 1] * nums[i - 1], nums[i - 1]);
                g[i] = Math.min(nums[i - 1], g[i - 1] * nums[i - 1]);
            }

            max = Math.max(max, f[i]);
        }

        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

题目链接
时间复杂度:O(n)
空间复杂度:O(n)

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

题目描述：

状态表示：
建立两个数组，f[i]表示以i位置为结尾的乘积为正数的最长子数组长度，g[i]表示以i位置为结尾的乘积为负数的最长子数组长度。
状态转移方程：
当nums[i]大于0时，f[i]=f[i-1]+1,g[i]=g[i-1]+1，但是其实g[i]这里的表示是有问题的，当g[i-1]等于0时逻辑上g[i]应该等于0，但是如果按照这个状态转移方程g[i]却等于1，所以需要修改为g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1。当nums[i]小于0时，f[i-1]=g[i-1]+1，这里也是一样当g[i-1]等于0是f[i]应该等于0而不是1，应该修改为当g[i-1]等于0时f[i]=0否则f[i]=g[i-1]+1 ,g[i]=f[i-1]+1。
初始化：
将f和g数组初始化为长度为n+1的数组，为了不影响最终的输出结果，根据状态转移方程，将g[0]和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 max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] < 0) {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            } else if (nums[i - 1] > 0) {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }
            max = Math.max(max, f[i]);
        }

        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题目链接
时间复杂度:
空间复杂度: