53. 最大子序和

给定一个整数数组 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 * 104
• -105 <= nums[i] <= 105  

1 解题思路

对于含有正数的序列而言，最大子序列肯定是正数，所以头尾肯定都是正数。我们可以从第一个正数开始算起，每往后加一个数便更新一次和的最大值；当当前和成为负数时，则表明此前序列无法为后面提供最大子序列和，因此必须重新确定序列首项。

2 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0){
                sum += num;
            } else {
                sum = num;
            }
            res = Math.max(res, sum);
        }
        return res;
    }
}

3 题目链接

https://leetcode-cn.com/problems/maximum-subarray/