最大子段和问题的动态规划求解 1. 基本原理 设数组为 a[k]，1≤k≤n，最大子段和 X 被定义为： X = max nj i 1 ≤≤≤ 不妨设： j ⎧ ∑ ⎨ ⎩ ik = ⎫ ka ][ ⎬ ⎭ jb ][ = max nj 1 ≤≤ ⎧ ⎨ ⎩ j ∑ mk = ⎫ ka ][ ⎬ ⎭ 其中 m 是可变的。注意：a[j]必须是 b[j]这个最大局部受限子段和所对应子段的最右端， 好好理解此处 j 和 b[j]的含义是整个算法的关键！ 根据 b[j]和 X 的定义，不难发现： X = jb ][max nj≤≤ 1 另一方面，根据 b[j]的定义，可以看出： 当 b[j-1]＞0 时，无论 a[j]为何值，b[j]=b[j-1]+a[j]； 当 b[j-1]≤0 时，无论 a[j]为何值，b[j]=a[j]； 所以有： 2. 具体实例 jb ][ = { jb [ max nj 1 ≤≤ ]1 +− }][ jaja [ ], k a[k] b[k] 1 3 3 2 -4 -1 3 2 2 4 10 12 其中：b[1]=a[1]，b[2]=b[1]+a[2]，b[3]=a[3]，b[4]=b[3]+a[4]；因此，对于数组 a 而言， 最大子段和为 b[4]，即 X=12。 3. 编程实现 略，针对数组 a 进行一遍扫描即可。算法实现的时间复杂度只有 O(n)。