53.最大子序和

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

示例 1：

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

每加入一个元素进入子序中，都需要判断其和

Solution1:动态规划

问题的关键在于 nums[i]到底是单独成为一段，还是加入到f{i-1}对应的那一段中去

这取决于nums[i]和f{i-1}+nums[i]的大小，如果前者比后者大，那么就是单独成为一段

f{i}只与f{i-1}有关，所以用一个变量pre来维护当前f{i}的f{i-1}的值

精髓在于 pre = Math.max(pre + x, x);，如果当前元素x本身比之前的累加和（包括x）还大，那么就从当前元素重新开始计数，这个思想是这道题的key

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maxSubArray(int[] nums) {
        // 初始化pre为0，pre用于记录到当前元素为止的最大子序和（包括当前元素）
        // 也就是说，pre是我们试图“构建”的当前最大子序和
        int pre = 0;
        
        // maxAns用于记录遍历过程中遇到的最大子序和，初始值设为数组的第一个元素，
        // 这是一个安全的起始值，因为最大子序和至少会是数组中的某个元素
        int maxAns = nums[0];
        
        // 遍历数组的每个元素
        for (int x : nums) {
            // 更新pre为当前元素x加上pre（如果pre是正数的话）和x本身之间的较大值
            // 这里的意思是，如果加上当前元素x能使得子序和增大，那么就加上x，
            // 否则，如果当前元素x本身比之前的累加和（包括x）还大，那么就从当前元素重新开始计数
            pre = Math.max(pre + x, x);
            
            // 更新maxAns为当前的pre（即到当前元素为止的最大子序和）和之前记录的maxAns中的较大值
            // 这样可以确保，无论在数组的哪个位置，maxAns总是存储着到目前为止的最大子序和
            maxAns = Math.max(maxAns, pre);
        }
        
        // 返回遍历完数组后的最大子序和
        return maxAns;
    }
}