# Max sum of k contiguous subarrays

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.