Maximum Subarray

1package pkg5leetcode;2 3/*4 * LeetCode 53: Maximum Subarray  (Medium)5 * ---------------------------------------6 * Find the contiguous subarray with the largest sum.7 *8 * APPROACH: Kadane's algorithm. Track best sum ending here; reset when it goes negative.9 * COMPLEXITY: Time O(n), Space O(1).10 */11public class leetcode5MaxSubArray {12 13    static int maxSubArray(int[] nums) {14        int best = nums[0], cur = nums[0];15        for (int i = 1; i < nums.length; i++) {16            cur = Math.max(nums[i], cur + nums[i]);   // extend or restart17            best = Math.max(best, cur);18        }19        return best;20    }21 22    public static void main(String[] args) {23        check(maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}) == 6, "mixed");   // [4,-1,2,1]24        check(maxSubArray(new int[]{1}) == 1, "single");25        check(maxSubArray(new int[]{5, 4, -1, 7, 8}) == 23, "mostly positive");26        check(maxSubArray(new int[]{-1, -2, -3}) == -1, "all negative");27        System.out.println("leetcode5MaxSubArray: all tests passed");28    }29 30    static void check(boolean cond, String name) {31        if (!cond) throw new AssertionError("FAILED: " + name);32        System.out.println("  PASS " + name);33    }34}