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
- 1 ≤ n ≤ 18
- -10 ≤ a[i] ≤ 10
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
- Unlike sums, a very negative product can become the maximum after one more negative number.
- 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