LEETCODE 53. Maximum Subarray 解题思路分析

题目大意：

最大子序和

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

示例:

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

进阶:

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=53

解题思路分析：

本题是一道经典的求连续子串和最大的问题。假设数组中所有元素都是正数，那么毫无疑问最大连续子串应该是数组本身。本题难点在于负数的存在，如果之前的和加上负数，总和会变小，那么我们如何确定最大子串区间呢？

我们先定义一个变量sum，代表区间[i, j]内所有数字和，如果当前下标为j的数字，大于区间[i, j]的总和，那么区间变为当前数字本身即可，即[j, j]。否则，区间右边界j加一，继续比较。举个例子，比如数组

[1, -5, 3, 4]

初始时，区间为[0, 0]，区间内数字和为1，当前数字1等于区间和1，移动右指针，区间变为[0, 1]，此时当前数字为-5，区间内和为-4，-5小于-4，继续移动右指针，区间变为[0, 2]，此时当前数字为3，区间内和-1，3大于-1，区间更新为[2, 2]，区间内和3，以此类推。每次区间范围发生变化时，使用区间内数值和更新全局最大和即可。

实现代码：

public int maxSubArray(int[] nums) {
    // 返回结果，默认为首元素
    int max=nums[0];
    // 区间内和
    int sum=0;
    // 循环每个数字
    for(int n : nums){
        // 累加区间和
        sum+=n;
        // 如果当前数字大于区间和，区间和设置为当前数字
        if(n>sum) sum=n;
        // 使用当前区间和更新全局最大区间和
        max=Math.max(max, sum);
    }
    return max;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 61.76% of Java online submissions for Maximum Subarray.

Memory Usage: 47.8 MB, less than 5.16% of Java online submissions for Maximum Subarray.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-53-maximum-subarray-解题思路分析/