DP最大子段和

动态规划处理“线”上的问题非常在行,今天我们就来探讨求解最大字段和的问题。 问题是这样的。 给定N个整数,要求求出最大的连续子段的和。 例如给定:1 -4 3 1 -2 其最大子段和为:4 该子段为:3 1 我们先来分析这个问题。我们最直观的方法就是穷举所有的子段并求和,找到其中最大的,即为答案,但是明显这样做,效率太低。题目中涉及到了“子段”,这使我们想到动态规划的通过寻找“最优子结构”来找到“最优解”的思路。 给定的N个数字存在数组A[N]当中,然后用B[N]来记录子段和的状态。读者可能有疑问,一个串的子串明显不会只有N个,那为什么只用N个元素来记录状态呢?这样做的原因正是因为我们使用动态规划的思路,B中存储的是状态,串中的每个数字的状态只考虑一次。 那么我们来考虑状态转移方程该如何构造: 假设我们已经得到了一个局部最大子串和B[K-1],考虑算上下一个元素A[K]的时候,这个子串的和为B[K] = B[K – 1] + A[K], 这里算出来B[K]如果大于或等于零,则一定有B[K