Given an array of integers and a number k, find knon-overlapping subarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

 

Example

Given [-1,4,-2,3,-2,3], k=2, return 8

Note

The subarray should contain at least one number

 

Analysis:

DP. d[i][j] means the maximum sum we can get by selecting j subarrays from the first i elements.

d[i][j] = max{d[p][j-1]+maxSubArray(p+1,i)}

we iterate p from i-1 to j-1, so we can record the max subarray we get at current p, this value can be used to calculate the max subarray from p-1 to i when p becomes p-1.

1 class Solution { 2 public: 3     /** 4      * @param nums: A list of integers 5      * @param k: An integer denote to find k non-overlapping subarrays 6      * @return: An integer denote the sum of max k non-overlapping subarrays 7      */ 8     int maxSubArray(vector
     
       nums, int k) { 9         // write your code here10         int n = nums.size();11         vector
      
       
        > dp(n + 1, vector
        
         (k + 1, INT_MIN));12         for (int i = 0; i <= n; ++i) 13             dp[i][0] = 0;14         for (int i = 1; i <= n; ++i) {15             for (int j = 1; j <= min(i, k); ++j) {16                 int tmp = 0;17                 for (int t = i - 1; t >= j - 1; --t) {18                     tmp = max(tmp + nums[t], nums[t]);19                     dp[i][j] = max(dp[i][j], tmp + dp[t][j-1]);20                 }21             }22         }23         return dp[nums.size()][k];24     }25 };
        
       
      
     

 

 重复使用dp数组，可以将空间复杂度降到O(n)。为了避免冲突，在枚举求解数组长度n时到倒着求，这样可以保证上一次迭代的结果不被覆盖掉。

1 class Solution { 2 public: 3     /** 4      * @param nums: A list of integers 5      * @param k: An integer denote to find k non-overlapping subarrays 6      * @return: An integer denote the sum of max k non-overlapping subarrays 7      */ 8     int maxSubArray(vector
     
       nums, int k) { 9         // write your code here10         int n = nums.size();11         vector
      
        dp(n + 1, 0);12         for (int j = 1; j <= k; ++j) {13             for (int i = n; i >= j; --i) {14                 dp[i] = INT_MIN;15                 int tmp = 0;16                 for (int t = i - 1; t >= j - 1; --t) {17                     tmp = max(tmp + nums[t], nums[t]);18                     dp[i] = max(dp[i], tmp + dp[t]);19                 }20             }21         }22         return dp[n];23     }24 };