LeetCode(DP)Maximum Subarray

2018-06-15

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

思路：首先能想到的肯定是枚举，利用两层for循环来计算所有可能出现的子序列的和，然后每次比较都要更新最大值的取值，不要最后获得了全部的序列和以后再排序，那样复杂度太高，通过不了，最好在每次比较后就更新最大值，最大值的初始值取Integer.MIN_VALUE最可靠，因为考虑到可能出现所有的数字都为负，且接近int型的最小值的情况。

代码如下：

//正向枚举
class Solution {
    public int maxSubArray(int[] nums) {
        int len=nums.length;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<len;i++){
            int sum=0;
            for(int j=i;j<len;j++){
                sum+=nums[j];
                max=Math.max(sum,max);
            }
        }
        return max;
    }
}

　　上述算法虽然可以解决问题，但是时间复杂度为O(N2)，我们得想办法优化，想到利用动态规划，但是动态规划需要子问题的迭代性够强，目前上述算法的规律性不够明显，我们是每次都是正向查找最大值，正向找不到规律时试着反方向找一下。我们写出反向查找的代码如下：

//反向查找
class Solution {
    public int maxSubArray(int[] nums) {
        int len=nums.length;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<len;i++){
            int sum=0;
            for(int j=i;j>=0;j--){
                sum+=nums[j];
                max=Math.max(sum,max);
            }
        }
        return max;
    }
}

我们假设有这样一个数组nums[]= {-1, 2, 3, -4}. 则上述算法的运行步骤就如下。

for i = 0 ⇒ max( sum(-1) )
for i = 1 ⇒ max ( sum(2), sum(2, -1) )
for i = 2 ⇒ max ( sum(3), sum(3, 2), sum(3, 2, -1) )
for i = 3 ⇒ max ( sum(-4), sum(-4, 3), sum(-4, 3, 2), sum(-4, 3, 2, -1) )

　　容易发现，每一次迭代时求得的都是以此次迭代的位置为终点的子数组的最大和，比如i=3时所求得的max就是以nums[３]结尾的所有子数组和的最大值。这样我们如果将每个以nums[i]结尾的子数组的最大和存下来记做dp[i]，这样在计算dp[i+1]的时候，可以这样简化:　如果dp[i]大于0，那么以A[i+1]结尾的子数组的最大和dp[i+1]必然等于nums[i+1]+dp[i] ，因为nums[i+1]为必加项，且dp[i]大于0，所以这个值肯定会更大；反之，若dp[i]<=0，则我们只取nums[i+1]当做dp[i+1]的值即可。

这样，我们就得到了一个可以迭代的子问题，即求出以nums[i]结尾的子数组的最大和dp[i]。然后再在这些dp[i]中找到最大值就是所求最大连续子序列之和。代码如下：

//动态规划算法
class Solution {
    public int maxSubArray(int[] nums) {
        int len=nums.length;
        int [] dp=new int [len];
        dp[0]=nums[0];
        int max=dp[0];
        
        for(int i=1;i<len;i++){
            if(dp[i-1]>0){
                dp[i]=dp[i-1]+nums[i];
            }else{
                dp[i]=nums[i];
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}