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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解:

思路一:

动态规划:

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

代码如下:

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)级别呢。 下边我们尝试做一下空间复杂度的优化。

优化代码如下:

// 定义状态 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结尾的子串的最大子序列和。 是否可行? 接下来我们尝试一下:

代码如下:

    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).

思路二:

分治策略

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

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

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

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

分治的应用:

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