53. Maximum Subarray

Posted on | Edited on | Views:

LeetCode

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
// Time Complexity: O(N), Space: O(N)
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp=new int[nums.length+1];
        int max=Integer.MIN_VALUE;
        dp[0]=0;
        for(int i=1;i<=nums.length;i++){
            dp[i]=Math.max(nums[i-1],dp[i-1]+nums[i-1]);
            max=Math.max(dp[i],max);
        }
        return max;
    }
}

DP, Kadane’s algorithm
1
2
3
4
5
6
7
8
9
10
11
12
// Time Complexity: O(N), Space: O(1)
class Solution {
   public int maxSubArray(int[] nums) {
		int maxCur=nums[0];
		int maxSoFar=nums[0];
		for (int i=1;i<nums.length;i++) {
			maxCur=Math.max(nums[i], maxCur+nums[i]);
			maxSoFar=Math.max(maxCur, maxSoFar);
		}
		return maxSoFar;
	}
}

link
Divide and Conquer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    private int maxSubArrayUtil(int[] nums, int l, int r) {
        if (l > r) {
            return Integer.MIN_VALUE;
        }
        int m = l + (r - l) / 2, ml = 0, mr = 0;
        // partition
        int lmax = maxSubArrayUtil(nums, l, m - 1);
        int rmax = maxSubArrayUtil(nums, m + 1, r);
        // merge
        for (int i = m - 1, sum = 0; i >= l; i--) {
            sum += nums[i];
            ml = Math.max(sum, ml);
        }
        for (int i = m + 1, sum = 0; i <= r; i++) {
            sum += nums[i];
            mr = Math.max(sum, mr);
        }
        return Math.max(Math.max(lmax, rmax), ml + mr + nums[m]);
    }
    
    public int maxSubArray(int[] nums) {
        return maxSubArrayUtil(nums, 0, nums.length - 1);
    }
}

0%