题解 | #连续子数组的最大和#
连续子数组的最大和
http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
这道题可以用动态规划法
每次遍历到某个值的时候，要不把它加到现有的总和上去，要不以它为头，从头开始计算总和。假设当前总和为s，当前遍历到的值为i，那么要对比s+i和i的大小，也就是看s是否大于0
先列举几种情况
| 当前总和（s） | 当前值 | 现和 | 决策 |
| 3 | -2 | 1 | ？ |
| 1 | 2 | 3 | 无脑加，总和为3 |
| -1 | 2 | 1 | 无脑不加，总和为2 |
| -1 | -2 | -3 | 无脑不加，总和为-2 |
即3，-2，6
这种情况，你会想如果当时从3加到-2过来该多好，总和就是7。而不是6了
所以，注意如果当前值小于0，但s大于0，不能停滞不前，虽然这会短暂地使总和变小
代码如下
max_value = -999 sum = 0 for i in array: if sum > 0: sum += i else: sum = i if sum > max_value: max_value = sum return max_value
投递多益网络等公司10个岗位