53. Maximum Subarray

题目 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

1,枚举

public class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 0){
            return 0;
        }
        
        int max = nums[0];
        for(int i=0; i<len; i++){
            for(int j=i; j<len; j++){
                int sum = 0;
                for(int k=i; k<=j; k++){
                    sum += nums[k];
                }
                
                max = (max > sum ? max : sum);
            }
        }
        return max;
    }
}

时间复杂度:O(n3) , 空间复杂度:O(1)

2,枚举优化最内层循环

分析:
因为当我们求得nums[i.....j]的时候, nums[i.....j-1]在上一步已经计算过了,不必再重复计算-----sum(i,j) = sum(i,j-1)+nums(j)

public class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 0){
            return 0;
        }
        
        int max = nums[0];
        for(int i=0; i<len; i++){
            int sum =0;
            for(int j=i; j<len; j++){
                sum += nums[j];
                max = (max > sum ? max : sum);
            }
        }
        return max;
    }
}

时间复杂度:O(n2) , 空间复杂度:O(1)

3,DP

状态方程:
i=0, f[0]=nums(0), max=nums[0]
i>0, f[i]= nums[i] + f(i-1) > 0 ? f(i) : 0,
        max = (max > f[i] ? max : f[i]);

public class Solution {
    
    public int maxSubArray(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        
        int[] memory = new int[nums.length];

        memory[0] = nums[0] ;
        int max = memory[0];
        for(int i=1, len=nums.length; i<len; i++){
            
            memory[i] = nums[i] + (memory[i-1] > 0 ? memory[i-1] : 0); 
    
            max = (max > memory[i] ? max : memory[i]);
        }
       return max;
    }
}

时间复杂度:O(n) , 空间复杂度:O(n)

4,贪心

分析:
假设我们知道nums[0...i-1]最大和的情况下,怎么计算nums[0...i]的最大和呢?
如果nums[0...i-1]是负数,那么我们认为它对nums[0...i]的最大和没有帮助,所以置nums[0...i-1]为0, nums[0...i]=nums[i]
如果nums[0...i-1]是大于等于0数,那么我们认为它对nums[0...i]的最大和有增加作用,那么nums[0...i]=nums[i]

public class Solution {
    
    public int maxSubArray(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        
        int max = Integer.MIN_VALUE;
        int sum = 0;
        
        for(int i=0, len=nums.length; i<len; i++){
            sum += nums[i];
            max = max > sum ? max : sum;
            
            if(sum < 0){
                sum = 0;
            }
        }
       return max;
    }
}