[LintCode] Maximum Subarray III

Maximum Subarray III
Given an array of integers and a number k, find k non-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<int> nums, int k) {

 9         // write your code here

10         int n = nums.size();

11         vector<vector<int>> dp(n + 1, vector<int>(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<int> nums, int k) {

 9         // write your code here

10         int n = nums.size();

11         vector<int> 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 };