Kadane算法

首先从leetcode53说起

这道题几年前第一次见到就折磨了我好久天，就算是看答案看半天也没有搞明白题解为什么是那样。最后就是CTRL+C、CTRL+V，放弃治疗，好像似乎是明白了这道题应该怎么解了。结果呢，过个几天，还是不会，过了一年，更加忘得没影了。瞬间觉得自己是傻逼，就自己这点智商，还当什么程序员，赶紧去找个电子厂上班吧。。。。


但看到评论区里面的各位兄弟，瞬间觉得自己不再孤单，所以今天想彻底将这个问题给吃透。

正文

思路：

1. 如果数组里面的数都是非负的，那么也就很好判断是哪个子数组的和是最大了，那当然是整个数组，数组越长越好。但是问题就在于数组里面有负数，情况就变得复杂起来。
2. 既然有负数，就只能换种思路了。
3. 像这种数组题，且求最大（最小）子数组，一看就知道需要使用DP(动态规划)。
4. DP的关键就在于写出那个状态转移方程。

数组中每一个位置上的数都可能成为最大子数组最后一位元素，所以我们可以动态规划的方式遍历一遍，求出各个位置上的最大值。

int curMax = nums[i];
for(int i = 1;i < nums.length;i++){
	curMax = Math.max(nums[i],curMax+nums[i]); // 以nums[i]结尾的子数组的最大和，curMax 很有可能是个负数，与其如此，不如数组只有nums[i]一个元素。
	dp = Math.max(dp,curMax);
}

解题误区：

1. 总想着找到具体是哪一个数组，然后再根据这个数组求出最大值。暴力法也不是不行，只是太low了。
2. 总以为一次Math.max 就能得到最终的结果。其实我们需要curMax 这个变量作为一个过渡。

Kadane算法

上面我分享的代码是不是看起来非常清爽，如果让我自己独立想出这个代码，我这辈子也是想不出来的，知道为什么吗？因为这可是CMU一名大学教授针对最大子数组和提出的Kadane算法。
所以作为普罗大众的芸芸众生想不出这个解法也是很合理的，也不必太过难为自己。自己目前能够想明白这个问题也没有什么了不起的，只不过是站在巨人的肩膀上。