leetcode-连续子数组的最大和

剑指 Offer 42. 连续子数组的最大和

[TOC]

题目如下：

方法：

1、动态规划

推想：

若nums数组的长度为n，下标则为0~n-1，用f(i)表示以第i个数结尾的连续子数组的最大和，故有：

$$
max{f(i)},0≤i≤n-1
$$

思路：

求出每段以第i个数结尾的子数组的f(i)，返回最大的f(i)即可

条件：

考虑nums[i]单独成一段还是加入f(i-1)这一段子数组，则可以通过判断nums[i] + f(i-1)和nums[i]的大小实现

$$
f(i) = max{nums[i]+f(i-1),nums[i]}
$$

代码实现：

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0;//存储f(i - 1)的值
        int maxSum = nums[0];
        for(int x : nums){
           pre = Math.max(x + pre, x);
           maxSum = Math.max(pre , maxSum);
        }
        return maxSum;
    }
}