题解 | #子数组的最大累加和问题#
子数组的最大累加和问题
http://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd
dp[i] 表示以arr[i]为结尾的最大子数组的最大累计和
每次比较的是,dp[i-1] + arr[i] 和 arr[i]
因为要求以arr[i]结尾,所以当dp[i-1] + arr[i],必然是连续的情况
arr[i] 更大,表示从arr[i]开始
数组:[1,-2,3, 5, -2, 6, -1]
dp : [1, -1,3, 8, 6, 12, 11]
因为要求空间复杂度为 O(1),所以改成一个变量就可以了!