原题
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.
给定一个整数数组和一个整数k,找出k个不重叠子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
例子
Input:
List = [-1,4,-2,3,-2,3]
k = 2
Output: 8
Explanation: 4 + (3 + -2 + 3) = 8
给出数组 [-1,4,-2,3,-2,3], 要求拆成2组
输出最大和为:8
原因:分成两组 [4]; [3,-2,3] => 4 + (3 + -2 + 3) = 8
思路
这是一道非常经典的动态规划的题目,主要解法称为”局部最优和全局最优解法“。基本思路是这样的,在每一步,我们维护两个变量,一个是全局最优,就是到当前元素为止最优的解,另一个是局部最优,也就是必须包含当前元素的最优解。
localMax[n][k]
定义了局部最优, 表示对于前n个数来说,分成k组必须将第n个元素包含
globalMax[n][k]
定义了全局最优, 表示对于前n个数来说,分成k组有可能不包含第n个元素
localMax[n][k]
在更新的过程中,由于第n个数必须被包含,则会出现两种情况:
1. 第n个元素单独为一组,意味着前 n-1个数分成 k-1组,当下全局最优解 globalMax[n-1][k-1]
2. 第n个元素与其他元素一起被分为k组,意味着其他n-1个元素已经构成了k组,且由于子数组下标位置连续,第(n-1)个元素一定出现在k组,当下局部最优解 localMax[n-1][k]
- 递推公式 localMax[n][k] = max(globalMax[n-1][k-1], local[n-1][k]) + 第n个元素
globalMax[n][k]
在更新的过程中,由于第n个数不确定是否包含,也会出现两种情况:
1. 第n个元素不被包含,意味着其他 n-1个元素需要构成k组,全局最优解是 globalMax[n-1][k]
2. 第n个元素被包含,意味着n个元素构成k组,当下局部最优解 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];
}
}
网友评论