原題
Description
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.
給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù)k待秃，找出k個(gè)不重疊子數(shù)組使得它們的和最大芬沉。
每個(gè)子數(shù)組的數(shù)字在數(shù)組中的位置應(yīng)該是連續(xù)的咆课。
返回最大的和棕孙。
例子
Input:
List = [-1,4,-2,3,-2,3]
k = 2
Output: 8
Explanation: 4 + (3 + -2 + 3) = 8
給出數(shù)組 [-1,4,-2,3,-2,3], 要求拆成2組
輸出最大和為：8
原因：分成兩組 [4]; [3,-2,3] => 4 + (3 + -2 + 3) = 8
思路
這是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃的題目拷恨，主要解法稱為”局部最優(yōu)和全局最優(yōu)解法“脖律。基本思路是這樣的腕侄，在每一步小泉，我們維護(hù)兩個(gè)變量，一個(gè)是全局最優(yōu)冕杠，就是到當(dāng)前元素為止最優(yōu)的解微姊，另一個(gè)是局部最優(yōu)，也就是必須包含當(dāng)前元素的最優(yōu)解分预。
localMax[n][k] 定義了局部最優(yōu), 表示對(duì)于前n個(gè)數(shù)來說兢交，分成k組必須將第n個(gè)元素包含
globalMax[n][k] 定義了全局最優(yōu), 表示對(duì)于前n個(gè)數(shù)來說，分成k組有可能不包含第n個(gè)元素
localMax[n][k] 在更新的過程中,由于第n個(gè)數(shù)必須被包含笼痹，則會(huì)出現(xiàn)兩種情況：
1. 第n個(gè)元素單獨(dú)為一組配喳，意味著前 n-1個(gè)數(shù)分成 k-1組，當(dāng)下全局最優(yōu)解 globalMax[n-1][k-1]
2. 第n個(gè)元素與其他元素一起被分為k組凳干，意味著其他n-1個(gè)元素已經(jīng)構(gòu)成了k組晴裹，且由于子數(shù)組下標(biāo)位置連續(xù)，第(n-1)個(gè)元素一定出現(xiàn)在k組救赐，當(dāng)下局部最優(yōu)解 localMax[n-1][k]
- 遞推公式 localMax[n][k] = max(globalMax[n-1][k-1], local[n-1][k]) + 第n個(gè)元素
globalMax[n][k] 在更新的過程中,由于第n個(gè)數(shù)不確定是否包含涧团，也會(huì)出現(xiàn)兩種情況：
1. 第n個(gè)元素不被包含，意味著其他 n-1個(gè)元素需要構(gòu)成k組经磅，全局最優(yōu)解是 globalMax[n-1][k]
2. 第n個(gè)元素被包含泌绣，意味著n個(gè)元素構(gòu)成k組，當(dāng)下局部最優(yōu)解 localMax[n][k]
- 遞推公式 globalMax[n][k] = max(globalMax[n-1][k], local[n][k])
完整代碼
public class Solution {
/**
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping subarrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
public int maxSubArray(int[] nums, int k) {
// write your code here
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int[][] localMax = new int[len + 1][k + 1];
int[][] globalMax = new int[len + 1][k + 1];
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= i && j <= k; j++) {
localMax[j - 1][j] = Integer.MIN_VALUE;
globalMax[j - 1][j] = Integer.MIN_VALUE;
localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1]) + nums[i - 1];
globalMax[i][j] = Math.max(localMax[i][j], globalMax[i - 1][j]);
}
}
return globalMax[len][k];
}
}
