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:

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.

DP time o(n),space o(n)

class Solution {
    public int maxSubArray(int[] nums) {
       int[] dp = new int[nums.length];
        
        dp[0] = nums[0];
        int res = nums[0];
        for(int i =1; i < nums.length; i++){
            dp[i] = nums[i] + (dp[i-1] > 0 ? dp[i-1] : 0);
            res = Math.max(res,dp[i]);
        }
        
        return res;
    }
}

time o(n), space o(1)

class Solution {
    public int maxSubArray(int[] nums) {     
        int res = nums[0];
       
        int sum = nums[0];
        
        for(int i = 1; i < nums.length;i++){
            sum = Math.max(sum+nums[i],nums[i]);
            res = Math.max(res,sum);
        }
        
        return res;
    }
}

divide and conquer time o(nlogn)

class Solution {
    public int maxSubArray(int[] nums) {
        
        
        
       return divid(nums,0,nums.length - 1);
        
    }
    
    
    public int divid(int[] nums, int start, int end){
        if(start == end)
            return nums[start];
        if(start + 1 == end){
            return Math.max(nums[start] + nums[end], Math.max(nums[start],nums[end]));
        }
        
        int mid = (start+end)/2;
        int lmax = divid(nums,start,mid-1);
        int rmax = divid(nums,mid+1,end);
        
        int mmax = nums[mid];
        int tmp = nums[mid];
        
        for(int i = mid -1 ; i >= start;i--){
            tmp += nums[i];
            if(tmp > mmax)
                mmax = tmp;
        }
        
        tmp = mmax;
        
        for(int i = mid + 1; i <= end;i++){
            tmp += nums[i];
            if(tmp > mmax)
                mmax = tmp;
        }
        
        return Math.max(mmax,Math.max(lmax,rmax));
    }
}

既能输出最大和，又能输出最大位置的算法

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int curMax = nums[0];
        int start = 0,end = 0;
        
        int[] res = new int[2];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
            int v = nums[i];
            
            if(curMax + v > v){
               curMax+= v;
                end++;
            }else{
                curMax = v;
                start = i;
                end = i;
            }
            
            if(curMax > max){
                max = curMax;
                res[0] = start;
                res[1] = end;
            }
        }
        System.out.println(res[0] + " "+ res[1]);
        return max;

    }
}