The question is: given an array of size $n$ and a number $m$, now our goal is to find AT MOST $m$ contiguous subarrays such that the sum of all these subarrays is the largest. It is also required that none of these subarrays can overlap.

Example: for an array [1, 2, 3, -2, 3, -10, 3], if $m = 2$, then the subarrays we take are [1, 2, 3, -2, 3] and [3], and their total sum is 10.

If $m = 4$, given the same array, then the subarrays we end up taking are [1, 2, 3], [3] and [3] and their total sum is 12 (we don't need the 4th subarray here).

Anyone has a solution?

I do have a dumb solution.
First, write a helper function maxSum() that finds the max sum subset within an interval of the array using Kadane’s algorithm (linear runtime).

Then, construct a dp[] array with size $n$, where dp[i] stores the largest value of sum of contiguous subarray within the interval $[0, i]$.

dp[i] = maxSum(0, i)

Lastly, repeat this step for $m - 1$ times:

for each i: 0 <= i < n:
  for each k: 0 <= k < i:
    dp[i] = max(dp[i], dp[k] + maxSum(k + 1, i))

This solution is $O(n^2 m)$ in runtime and $O(n^2)$ in space if we store results from maxSum() in advance, and $O(n^3 m)$ in runtime $O(n)$ in space if we do not store it in advance. I believe there is definitely a way to do better.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.