一、问题描述
现在给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6
示例2：
输入：nums = [1] 输出：1
示例3：
输入：nums = [5,4,-1,7,8] 输出：23
二、问题分析
这是一道经典的动态规划的题目，假设nums数组的长度为n，那么nums数组的下标为0到n-1。
我们用 f ( i ) 表示数组中以第 i 个数结尾的连续子数组的最大和，那么我们要求解的问题就变成了：
max{ f ( i ) }，其中 0 <= i <= n-1
我们只需要求出每个 f ( i ) 的值，然后求出它们中的最大值返回即可。因此我们现在要考虑的就是如何求出 f ( i ) 的值。想要求 f ( i ) 的值，我们可以先求出 f ( i-1) 的值，即以第 i-1 个数结尾的连续子数组的最大和，然后判断当nums[ i ] 加入后以第 i 个数结尾的连续子数组的最大和的变化情况，也就是判断现在的连续子数组的最大和是 f ( i - 1) + nums[ i ] 还是 nums[ i ]，将二者中的较大值赋值给 f ( i ) ，于是我们可以得到这样的动态规划转移方程：
f ( i ) = max{ f( i − 1 ) + nums[ i ]，nums[ i ] }
这样我们可以用一个变量 maxValue 来保存当前每个 f ( i ) 中的最大值，用一个变量 pre 来维护对于当前 f ( i ) 的 f ( i - 1 ) 的值是多少，采用了类似于“滚动数组”的思想。
三、代码实现
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0; //表示当前f(i)的f(i-1)的值
int maxValue = nums[0]; //表示当前最大的f(i)的值
for(int x : nums){
//pre在更新前表示当前f(i)的f(i-1)的值，pre更新后表示新的f(i)的值
pre = Math.max(pre + x , x);
//判断是当前新的f(i)的值大还是之前记录的f(i)的值大，然后对maxValue的值进行更新
maxValue = Math.max(maxValue,pre);
}
return maxValue; //循环结束后，返回的maxValue即为连续子数组的最大和
}
}
