[LeetCode-53] 最大子序和

发布于个人公众号,打开微信,搜索MelodyJerry即可
[LeetCode-53] 最大子序和## 53. 最大子序和

LeetCode官方的难度定位为简单,个人觉得可以达到中等的!!!

难度 简单 通过率 54.64%
(571,167/1,045,196)

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

示例 1:

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

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [0]
输出:0

示例 4:

输入:nums = [-1]
输出:-1

示例 5:

输入:nums = [-100000]
输出:-100000

提示:

  • 1 <= nums.length <= 3 ∗ 1 0 4 3 * 10^4 3∗104
  • − 1 0 5 -10^5 −105 <= nums[i] <= 1 0 5 10^5 105

进阶:

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

题解

① 动态规划

  • 值得注意的是题目描述中是连续,所以这里直接用动态规划就可以AC了。
  • 状态转移方程:
    • dp[i] = max(dp[i-1] + nums[i], nums[i])
      • dp[i]: 以nums[i]结尾的子数组的和的最大值
    • 为什么是dp[i-1]+nums[i]
      • 思考dp[i-1]是否会对nums[i]带来负增益
      • 若带来负增益,自然是nums[i]值比dp[i-1]+nums[i]值更大
    • 初始条件:dp[0] = nums[0]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-urKgsuGc-1626534999894)(https://gitee.com/melodyjerry163/filebed/raw/master//carbon(2)].png)

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0]; // 初始条件
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            /** 状态转移方程: 
             *  dp[i] = max(dp[i-1] + nums[i], nums[i])
             *  dp[i]: 以nums[i]为右区间的子数组的和的最大值
             */
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            /* 等价于
            if (dp[i - 1] >= 0) 
                dp[i] = dp[i - 1] + nums[i];
            else 
                dp[i] = nums[i];
            */
            max = Math.max(max, dp[i]); //更新max
        }
        return max;
    }
}

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( n ) O(n) O(n)

② 优化后的动态规划

这个优化主要是减少了空间复杂度

在上面的状态转移方程中提到:

  • 为什么是dp[i-1]+nums[i]
    • 思考dp[i-1]是否会对nums[i]带来负增益,若带来负增益,自然是nums[i]值比dp[i-1]+nums[i]值更大

再看看代码中的这段注释:

/* 等价于
if (dp[i - 1] >= 0) 
    dp[i] = dp[i - 1] + nums[i];
else 
    dp[i] = nums[i];
*/

关键就是这里了,这里就很好地解释了那个思考:

  • 思考 dp[i-1]是否会对nums[i]带来负增益

因此根据这段代码,可以对上面的动态规划做个小优化,

  • 关键在于sum>=0这个判断
    • sum<0时候,对当前的新整数num一定会造成负增益
      • sum+num一定<num
      • 所以最大子数组的和一定不会再继续加当前整数
class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE; // 这是个注意点
        int sum = 0;
        for (int num : nums) {
            if (sum >= 0) 
                sum += num;
            else 
                sum = num;
            max = Math.max(max, sum); //更新max
        }
        return max;
    }
}

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( 1 ) O(1) O(1)

另一个版本的优化,其实也差不多的,容易理解。

该算法更为简便之处是忽略了对子序列的寻找比较,而是根据规律直接找出最佳答案。

对于含有正数的序列而言,最大子序列肯定是正数,所以头尾肯定都是正数。我们可以从第一个正数开始算起,每往后加一个数便更新一次和的最大值;当当前和成为负数时,则表明此前序列无法为后面提供最大子序列和,因此必须重新确定序列首项。

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = 0 , thisSum = 0;
        for( int i = 0; i < nums.length ; i++ ){
            thisSum += nums[i];
            if(thisSum > maxSum)
                maxSum = thisSum;
            else if(thisSum < 0)
                thisSum = 0;
        }
        return maxSum;
    }
}

③ 分治法

  • 其实就是它的最大子序和要么在左半边,要么在右半边,要么是在中间
  • 对于左、右边的序列,情况也是一样,因此可以用递归处理。
    • 递归的基本边界:左、右为相同位置的元素,即只有一个元素.
  • 中间部分的则可以直接计算出来。

以下是LeetCode官方题解的分治算法:

来源:最大子序和 - LeetCode官方题解- 方法二:分治

class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }
}

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( l o g   n ) O(log\,n) O(logn)


建议阅读一下李威威同学的经典动态规划问题(理解「无后效性」)

上一篇:剑指 Offer 53 - II. 0~n-1中缺失的数字


下一篇:练习一下linux中的list函数。