1. 问题
输入一个整数数组，在其中找出一个最大的连续子数组，返回子数组的和。
例如:nums=[-3,1,3,-1,2,-4,2]
返回5，因为[1,3,-1,2]是最大连续子数组。
2. 思路
2.1 定义base case
当数组只有一个元素时，这个元素就是最大子数组的和。
2.2 定义dp数组
先定义dp数组，假设dp[i]表示以nums[i]结尾的最大子数组和。那么要求最大子数组的话，就是求dp数组的最大值。
int res = Integer.MIN_VALUE;
for (int i = 0; i < dp.length; i++){
res = Math.max(res,dp[i]);
}
2.3 定义状态转移方程
用数学归纳法进行证明，假定已计算出dp[i-1]，那么dp[i]的值只有两种情况:
- dp[i-1]是最大子数组的和
- dp[i-1] + nums[i]是最大子数组的和
所以方程为dp[i] = Math.max(dp[i-1] + nums[i], dp[i-1]);
代码:
public int maxSubArray(int[] nums){
if(nums == null || nums.length) return 0;
int n = nums.length;
int[] dp = new int[n];
//base case
dp[0] = nums[0];
for (int i = 0; i < n; i++){
dp[i] = Math.max(dp[i-1]+nums[i], dp[i-1]);
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++){
res = Math.max(res, dp[i]);
}
return res;
}
2.4 状态压缩
考虑到dp[i]只和dp[i-1]有关，即dp_1的状态只和dp_0有关，所以可以进行状态压缩，整体代码如下:
package LeetCode.dp;
/**
* 求最大连续子数组和
*/
public class MaxSubArray {
public static void main(String[] args) {
int[] nums = new int[]{-3,1,3,-1,2,-4,2};
System.out.println(calMaxSubArray(nums));
}
public static int calMaxSubArray(int[] nums){
if (nums == null || nums.length == 0){
return 0;
}
int res = Integer.MIN_VALUE;
int n = nums.length;
int dp_0 = nums[0];
int dp_1 = 0;
for (int i = 0; i < n; i++ ){
dp_1 = Math.max(dp_0, dp_0 + nums[i]);
dp_0 = dp_1;
res = Math.max(res,dp_1);
}
return res;
}
}
