leetcode-program

Question 53: Maximum Subarray

Link

Solution

Solution 1: DP

Use sum[i] to represents the maximum subarray that ends with the i-th number nums[i]. See the code for details.

Solution 2: Divide and Conquer

Divide a sequence of number a to two parts: a[:mid] and a[mid:]. The answer may be found in the following three cases:

• the maximum subarray of a[:mid],
• the maximum subarray of a[mid:], and
• the concatenation of: the maximun subarray of a[:mid] ending with the mid - 1-th element, and the maximum subarray of a[mid:] starting with the mid-th element.

This is an O(log(N)) algorithm.

Code

Java

public class Solution {
    public int maxSubArray(int[] nums) {
        // return solveWithDp(nums);
        return solveWithDivideAndConquer(nums, 0, nums.length).max;
    }

    private int solveWithDp(int[] nums) {
        int[] sum = new int[nums.length];
        sum[0] = nums[0];

        int ans = sum[0];
        for (int i = 1; i < nums.length; ++i) {
            if (sum[i - 1] < 0) sum[i] = nums[i];
            else sum[i] = sum[i - 1] + nums[i];
            ans = Math.max(ans, sum[i]);
        }

        return ans;
    }

    private Subarray solveWithDivideAndConquer(int[] nums, int l, int r) {
        if (l + 1 == r) return new Subarray(nums[l]);

        int mid = (l + r) / 2;
        Subarray left = solveWithDivideAndConquer(nums, l, mid);
        Subarray right = solveWithDivideAndConquer(nums, mid, r);

        int leftMax = Math.max(left.leftMax, left.sum + right.leftMax);
        int rightMax = Math.max(right.rightMax, right.sum + left.rightMax);
        int max = Math.max(left.rightMax + right.leftMax, Math.max(left.max, right.max));
        int sum = left.sum + right.sum;

        return new Subarray(leftMax, rightMax, max, sum);
    }

    private static class Subarray {
        int leftMax;
        int rightMax;
        int max;
        int sum;

        Subarray(int value) {
            leftMax = value;
            rightMax = value;
            max = value;
            sum = value;
        }

        Subarray(int leftMax, int rightMax, int max, int sum) {
            this.leftMax = leftMax;
            this.rightMax = rightMax;
            this.max = max;
            this.sum = sum;
        }
    }
}

This site is open source. Improve this page.