Maximum Subarray Sum

http://www.lintcode.com/en/problem/maximum-subarray/

Question

Given an array of integers, find a contiguous subarray which has the largest sum.

Example

Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Analysis

DP和Greedy均可进行求解，不过还是更推荐使用DP，因为Greedy很多情况下都是不正确的。

Dynamic Programming:

maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i];

Kadane's Algorithm

Solution

Brute-force Compare all subarray sum (119 ms 2.49% AC)

// Compare all subarray sum: O(n^2)
class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int sum;
        for (int i = 0; i < nums.length; i++) {
            sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                maxSum = Math.max(sum, maxSum);
            }
        }
        return maxSum;
    }
}

Improvement O(n) (7ms 93.68% AC)

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

Dynamic Programming

// Dynamic Programming: O(n)
// Similar idea to Greedy Algorithm

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n]; //dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];

        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

Greedy Algorithm

// Greedy Algorithm: O(n)
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum = sum + nums[i];
            max = Math.max(sum, max);
            sum = Math.max(sum, 0);
        }
        return max;
    }
}

Prefix Sum

public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int max = Integer.MIN_VALUE, min = 0;
        int prefixSum = 0;
        for(int i = 0; i < nums.length; i++){
            prefixSum += nums[i];
            max = Math.max(max, prefixSum - min);
            min = Math.min(min, prefixSum);
        }

        return max;
    }
}

Kadane's Alogrithm

public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int cur = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
            cur = Math.max(nums[i], cur + nums[i]);
            max = Math.max(max, cur);
        }

        return max;
    }
}

Related Problems

Maximum Subarray II

Maximum Subarray III

Maximum Subarray IV

Reference

PreviousIntersection of Two Arrays IINextMinimum Subarray Sum

Last updated