每天一题LeetCode【第38天】

T53. Maximum Subarray【Easy】

题目

给一个数组，找到和最大的连续序列。

例如，给出数组 [-2,1,-3,4,-1,2,1,-5,4],

连续序列 [4,-1,2,1] 的和最大，是 6.

思路

这是一道 Easy 题，直接看代码也会很简单~

思路关键有两个点：

① 找出各个连续序列的最大和

② 比较它们的大小，返回大的那个值

然后就是看代码就好啦~

代码

代码取自 Top Solution，稍作注释

public int maxSubArray(int[] nums) {
        int maxSoFar=nums[0], maxEndingHere=nums[0];
        for (int i=1;i<nums.length;++i){
            //maxEndingHere表示往下找到那个连续序列的最大和
            maxEndingHere= Math.max(maxEndingHere+nums[i],nums[i]);
            //maxSoFar来保存到现在为止的最大的和
            maxSoFar=Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }