I'm trying to solve the following problem (from VOI 2005).
Given a sequence
n numbers, find the minimum
M such that there's a way to split sequence a into
k non-empty continuous subsequence and the total sum of each subsequence does not exceed
1 <= k <= n <= 15000,
|ai| <= 30000,
ai may be negative.
The best solution I can come up for this problem is the following O(n^2*k) DP solution:
f[i][k] the minimum value
M for the sequence that contain first
d[i] the sum of the first
i number of sequence. Then we have the following formula:
f[i][k] = min(max(f[j][k-1], d[i]-d[j])) (with
0 <= j < i)
Of course, with such big constrains, this solution is not fast enough. Is there a faster solution for this? Thanks in advance.