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
, and their total sum is 10.
If $m = 4$, given the same array, then the subarrays we end up taking are
[1, 2, 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.