1
$\begingroup$

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?

--Edited
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.

$\endgroup$

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.