[LeetCode]题解(Java) 053 Maximum Sub Array 最大子序和

刷知乎忽然看到的一道题,然后上leetcode上看了一下,虽然标记的是easy,但是第一反应居然只想到o(n^3)暴力法……仔细思考了好久,才找到o(n)的解法,非奇思妙想不可得。详情请看一下代码注释。

描述

官方地址

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

Java Solution

code

  • ✔ Accepted
  • ✔ 202/202 cases passed (16 ms)
  • ✔ Your runtime beats 31.02 % of java submissions
  • ✔ 2019-02-12 21:31:45
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0){
            return 0;
        }
        int sum = nums[0];  //sum保存着跟随idx遍历nums每个索引为结束位置的最大值(不是太好理解)
        int max = nums[0];  //max保存着idx及其以前的元素为结束位置的最大值
        for ( int idx = 1; idx < nums.length; ++idx){   //注意idx从1开始,因为sum和max不能初始化为0,
                                                    //只能初始化为nums[0],因为nums中的元素可能是负数
            sum = Math.max(sum + nums[idx], nums[idx]); //注意sum是以idx索引元素为结束位置的最大值(包含idx)
            max = Math.max(sum, max);   //
        }
        return max;
    }
}
(max: 全局的最大值,也就是我们要求的结果; sum: 局部最大值,代表的是以某元素结尾的最大值)
    -1 2 -3 4 -1
    idx = 0: sum = -1, max = -1 (注: 此步骤即是初始化sum和max,
        也就是第一个元素为结尾的局部最大值和全局最大值)
    idx = 1: sum = (-1 + 2), max = sum = 1
    idx = 2: sum = (1 + -3), max = 1
    idx = 3: sum = 4, max = sum = 4
    idx = 4: sum = (4 + -1), max = 4
    所以求得结果max=4, 感觉很奇妙有木有!
    注意到此题有dp解法,后续增加
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • <center>#1 Two Sum</center> link Description:Given an arr...
    铛铛铛clark阅读 2,226评论 0 3
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,962评论 2 36
  • 前言 2. 实现 Singleton 3. 数组中重复的数字 4. 二维数组中的查找 5. 替换空格 6. 从尾到...
    Observer_____阅读 3,015评论 0 1
  • 免费一词总是能吸引人们的目光,在没有看着本书之前我绝对没想到关于免费也会有这么一类的介绍,在书中作者对免费这种商业...
    6313170f2e94阅读 1,757评论 0 0
  • 追寻的路 没有想像的多彩 只是一条光秃秃的小路 似乎想添加点什么 却惶恐不...
    辛怡璞子阅读 150评论 0 0