I'm trying to solve the following problem (from VOI 2005).
Given a sequence a
with 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 M
.
Constrains: 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:
Call f[i][k]
the minimum value M
for the sequence that contain first i
numbers, 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.