Maximum Product Subarray

1package pkg5leetcode.blind75;2 3/*4 * Maximum Product Subarray | LC 1525 * APPROACH: Track max and min product ending at each index (negatives flip).6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class blind75_LC152MaximumProductSubarray {9    static int maxProduct(int[] nums) {10        int best = nums[0], max = nums[0], min = nums[0];11        for (int i = 1; i < nums.length; i++) {12            if (nums[i] < 0) { int t = max; max = min; min = t; }13            max = Math.max(nums[i], max * nums[i]);14            min = Math.min(nums[i], min * nums[i]);15            best = Math.max(best, max);16        }17        return best;18    }19 20    public static void main(String[] args) {21        check(maxProduct(new int[]{2, 3, -2, 4}) == 6, "case1");22        check(maxProduct(new int[]{-2, 0, -1}) == 0, "case2");23        System.out.println("all tests passed");24    }25 26    static void check(boolean cond, String name) {27        if (!cond) throw new AssertionError("FAILED: " + name);28        System.out.println("  PASS " + name);29    }30}