53. 最大子序和DP

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-subarray 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路一：

动态规划：

定义dp数组的状态是以i结尾的子序列的最大子序列和(必须包含i).
设置初始状态,dp[0] 就是nums[0].
当dp[i-1] > 0时，dp[i]为dp[i-1] + nums[i]。当dp[i - 1] <= 0时,dp[i] 为 nums[i].

代码如下：

 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


public int maxSubArray(int[] nums) {

        // 定义状态 dp[i] 是以i结尾的最大子序列和
        int[] dp = new int[nums.length];

        // 定义初始值 dp[0] 就是数组的第一个元素
        dp[0] = nums[0];

        // 用来存储最终的最大值
        int maxVal = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (dp[i - 1] > 0){
                // 当dp[i-1] > 0是时，则dp[i] 是前一个 加上 当前num
                dp[i] = dp[i - 1] + num;
            }else {
                // 当dp[i-1] <= 0时，则dp[i]就是当前的 num
                dp[i] = num;
            }
            // 记录dp数组的最大值
            maxVal = Math.max(dp[i], maxVal);
        }
        return maxVal;
    }

复杂度分析：

算法时间复杂度：O(N)

空间复杂度: O(N) 因为用到了额外的dp数组存储

优化：

该算法时间复杂度我们已经做到O(N)级别，不可再优化了。但是空间复杂度可以继续优化，因为上述计算中我们发现，在计算dp[i]时，我们只用到了dp[i-1] 和 num. 是否可以优化空间复杂度至O(1)级别呢。下边我们尝试做一下空间复杂度的优化。

优化代码如下：

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


// 定义状态 dp[i] 是以i结尾的最大子序列和
        int[] dp = new int[nums.length];

        // 定义初始值 dp[0] 就是数组的第一个元素
        int prev = nums[0];

        // 用来存储最终的最大值
        int maxVal = prev;

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (prev > 0){
                // 当dp[i-1] > 0是时，则dp[i] 是前一个 加上 当前num
                prev += num;
            }else {
                // 当dp[i-1] <= 0时，则dp[i]就是当前的 num
                prev = num;
            }
            // 记录dp数组的最大值
            maxVal = Math.max(prev, maxVal);
        }
        return maxVal;

以上代码中，我们使用了一个变量 prev 代替了数组dp。实现了空间复杂度为O(1)的优化。其时间复杂度仍然是O(N)。

第二种优化:

上述优化中，我们使用了 prev 变量代替了dp数组，实现了空间复杂度的优化。经观察我们发现，是否不利用额外变量，而直接使用nums数组存储呢？从左到右递推时，我们直接将nums数组中的元素，改为以当前index结尾的子串的最大子序列和。是否可行？接下来我们尝试一下：

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


    public int maxSubArray2(int[] nums) {

        // 用来存储最终的最大值
        int maxVal = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (nums[i - 1] > 0){
                // 当dp[i-1] > 0是时，则dp[i] 是前一个 加上 当前num
                nums[i] = nums[i - 1] + num;
            }else {
                // 当dp[i-1] <= 0时，则dp[i]就是当前的 num
                // 可以忽略else， 引文nums[i]本来就是num， 不需要重新赋值
                // nums[i] = num;
            }
            // 记录dp数组的最大值
            maxVal = Math.max(nums[i], maxVal);
        }
        return maxVal;
    }

以上代码中，我们直接使用了nums原数组作为存储最终结果的数组，没有利用多余的内存空间，空间复杂度仍然是O(1). 时间复杂度为O(N).

思路二：

分治策略

分治：也就是分而治之。它的一般步骤是：

将原问题分解成若干个规模较小的子问题(子问题和原问题结构一样，只是规模不一样)
子问题又不断分解成规模更小的子问题，直到不能分解(直到可以轻易计算出子问题的解)
利用子问题的解推导出原问题的解

因此，分治策略非常适合递归

需要注意的是，子问题之间是相互独立的。

分治的应用：

快速排序，归并排序，大数乘法。

Contents