求K个子段的最大和问题

Question

就是最大子段的变形，求一个数列的k个子段，使这K个子段的和最大。
希望简单说一下思路，还有状态转移方程

Answer 1

用递归来做吧
f(int * a,int begin,int end,int k)表示a[begin..end]这个序列取k个子段，子段的最大的和
f(a,begin,end,k) = max( f(a,begin,begin + i,1) + f(a,begin + i,end,k-1) ) (begin <= i < end)
这里根据i把a[begin..end]分成a[begin..begin+i]和a[begin+i,end]两段，第一段取一个字段，后一段取k-1个字段
遍历所有的i，取得的最大值就是在a[begin..end]中取k段的最大值
而f(a,begin,begin + i,1)就是求最大子段的问题