清华大学出版社 最大m子段和问题 给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,以及 个正整数m,要求确定序列的m个不相交子段,使这m个子段的总 和达到最大。 设b(i,j表示数组a的前项中个子段和的最大值,且第个子段 含a](1≤i≤m,j≤n)。则所求的最优值显然为mwxb(m 与最大子段和问题类似地,计算b(,〕的递归式为 b(2j)=max{b(i,-1)+a[门,maxb(i-1,t)+a门}(l≤i≤m,i≤j≤n) i-1≤<j 初始时,b(0,j)=0,(1≤j≤n;b(,0)=0,(1≤i≤m)。 优化:注意到在上述算法中,计算b[时只用到数组b的第i-1 行和第行的值。因而算法中只要存储数组b的当前行,不必存 储整个数组。另一方面,b(i-1,t)的值可以在计算第i1行时预 先计算并保存起来。计算第行的值时不必重新计算,节省了计 算时间和空间。8 最大m子段和问题 给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,以及一 个正整数m，要求确定序列的m个不相交子段，使这m个子段的总 和达到最大。 设b(i，j)表示数组a的前j项中i个子段和的最大值，且第i个子段 含a[j](1 i m，i j n)。则所求的最优值显然为 与最大子段和问题类似地，计算b(i，j)的递归式为 初始时，b(0，j)=0，(1 j n);b(i，0)=0，(1 i m)。 max b(m, j) m jn ( , ) max{ ( , 1) [ ], max ( 1, ) [ ]} (1 , ) 1 b i j b i j a j b i t a j i m i j n i t j = − + − +     −   优化：注意到在上述算法中，计算b[i][j]时只用到数组b的第i-1 行和第i行的值。因而算法中只要存储数组b的当前行，不必存 储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预 先计算并保存起来。计算第i行的值时不必重新计算，节省了计 算时间和空间