给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
首先我们来分析题意：我们设定f(n)为数组长度为n的最大子序和
我们分析
当n=1时 需要比较的数组组合为 [1]
当n=2时 需要比较的数组组合为 [1][2][1,2]
当n=3时 需要比较的数组组合为 [1][2][1,2][3][3,2][3,2,1]
当n=4时 需要比较的数组组合为 [1][2][1,2][3][3,2][3,2,1][4][4,3][4,3,2][4,3,2,1]
当n=5时 需要比较的数组组合为 [1][2][1,2][3][3,2][3,2,1][4][4,3][4,3,2][4,3,2,1][5][5,4][5,4,3][5,4,3,2][5,4,3,2,1]
分析比较n值变换时候消除不同n值之间重复的组合
最终可以得到变形后需要比较的数组队列
当n=1时 需要比较的数组组合为 [1]
当n=2时 需要比较的数组组合为 [2] [1,2]
当n=3时 需要比较的数组组合为 [3] [3,2] [3,2,1]
当n=4时 需要比较的数组组合为 [4] [4,3] [4,3,2] [4,3,2,1]
当n=5时 需要比较的数组组合为 [5][5,4][5,4,3][5,4,3,2][5,4,3,2,1]
设定第n层所有需要比较的子序数组为 f(n)
比较相邻两层之间的数据可以知道 f(n)中的数组相当于 [n]和f(n-1)的数组循环加[n]元素
设定dp[n]为第n层中需要比较的最大子序和
dp[n] = max([n],[n]+dp[n-1])
public int maxSubArray(int[] nums) {
int position = nums[0];
int result = position;
for(int i=1;i<nums.length;i++) {
position = Math.max(nums[i], position+nums[i]);
result = Math.max(result,position);
}
return result;
}
