Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Maximum Product Subarray

Medium · Arrays · Asked at Amazon, Microsoft, Google, Uber

Find the maximum product of a non-empty contiguous subarray.

Input

First line: n. Second line: n space-separated integers.

Output

The maximum product.

Constraints

Keep both the maximum and the minimum product ending at each index — a negative number swaps them.

Example 1

Input

4
2 3 -2 4

Output

6

Example 2

Input

3
-2 0 -1

Output

0

Hints

  1. Unlike sums, a very negative product can become the maximum after one more negative number.
  2. Track both the maximum and the minimum product ending at each index.

Approach

For each index keep hi and lo, the largest and smallest products of a subarray ending there. The new values come from three candidates: x, hi × x and lo × x. Multiplying by a negative x swaps the roles of hi and lo, which is why lo matters. The answer is the largest hi seen. With n ≤ 18 and |a[i]| ≤ 10, products stay within 10^18, which fits in 64 bits.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long x;
    cin >> x;
    long long hi = x, lo = x, best = x;
    for (int i = 1; i < n; i++) {
        cin >> x;
        long long a = hi * x, b = lo * x;
        hi = max(x, max(a, b));
        lo = min(x, min(a, b));
        best = max(best, hi);
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
a = data[1 : data[0] + 1]
hi = lo = best = a[0]
for x in a[1:]:
    cands = (x, hi * x, lo * x)
    hi, lo = max(cands), min(cands)
    best = max(best, hi)
print(best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long x = sc.nextLong();
        long hi = x, lo = x, best = x;
        for (int i = 1; i < n; i++) {
            x = sc.nextLong();
            long a = hi * x, b = lo * x;
            hi = Math.max(x, Math.max(a, b));
            lo = Math.min(x, Math.min(a, b));
            best = Math.max(best, hi);
        }
        System.out.println(best);
    }
}

Solve Maximum Product Subarray online · All practice problems