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.