LintCode-Maximum Subarray III - LiBlog - 博客园

LintCode-Maximum Subarray III - LiBlog - 博客园

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

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.

Read full article from LintCode-Maximum Subarray III - LiBlog - 博客园