问题: 给定一整数序列A1,
A2,... An (可能有负数),求A1~An的一个子序列Ai~Aj,使得Ai到Aj的和最大
例如:整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。
从左到右记录当前子序列的和sum,开始位置为start,结束位置为end。若sum不断增加,那么最大子序列的和max也不断增加(不断更新max,start,end)。如果往前扫描中遇到负数,那么当前子序列的和将会减小。此时sum
将会小于max,当然max也就不更新。如果sum降到0时,说明前面已经扫描的那一段就可以抛弃了,这时将sum置为0,并且start为下一个位......
阅读全文