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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

LEETCODE 53. Maximum Subarray 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 152. Maximum Product Subarray 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。