面试题：最大子段和

summary

:

面了两家公司，都是这个题，都不会做。不管以后还去不去面试，我都 一定 要把这 货给解决！

学了四年计算机，四年了，始终无法理解动态规划的精妙，能看懂，但是叫我想，我想不 出来。贪心思想，都能说，但是真正要运用，却不会。有的时候，智商问题就是无解。

假定给一个序列为：-10 1 2 3 4 -5 -23 3 7 -21。

开始分析。不管是用暴力方法还是用动态规划的方法，都必须要用一个数存放目前最大的 子段和，就用sum来记录吧。每得到一个临时的子段和，都要和这个最大的子段和比较， 如果临时的子段和较大，则更新，这个临时的子段和就叫temp_sum吧。有的时候，可能 要求输出最大子段和的子序列是从哪里到哪里的，那就要用begin和end记录一下了。

好，现在关键点到了，遍历这个序列，对于每个元素，先看之前计算过的temp_sum是否 比0大， 如果小于或者等于0，那这个temp_sum就有负作用，为什么不直接从当前这个元素开始呢？ ，所以这个时候就把temp_sum的值设置为当前元素的值。如果大于0,那么 说明继续拿当前这个元素还是很有用， 不管它是正数还是负数，先拿了再说 ，这就 叫 贪心 。这个时候，用temp_sum的值再和sum比较，如果temp_sum比较大，那么 就应该更新sum为temp_sum，同时把end更新，如果sum比较大，说明刚刚加的这个数有负 作用，不能加这个数，那么end就不要修改了。继续这个过程，直到结束。

代码：

::: {.code-include lexer="cpp"} ./max-subseq-sum.cpp :::