[LeetCode-53] 最大子序和

本文主要是介绍[LeetCode-53] 最大子序和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

给定一个整数数组 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)

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

这篇关于[LeetCode-53] 最大子序和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！