What it teaches: Carrying two states: a negative number turns the smallest product into the largest.
Practise it on judges as “Maximum Product Subarray”.
The problem
Return the largest product of a non-empty contiguous subarray.
Example 1
Input: nums = [2, 3, -2, 4]
Output: 6
Example 2
Input: nums = [-2, 3, -4]
Output: 24
Constraints
1 ≤ n ≤ 2 × 10⁴
The answer fits in an int
Pattern clues in the wording
→ Kadane-like, but with multiplication and signs
These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.
Stuck? Take one hint at a time
Solution.java · starter
class Solution {
public int maxProduct(int[] nums) {
return 0;
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
For each x: candidates are x, hi × x, lo × x. New hi = max of them, new lo = min of them.
Approach 1
class Solution {
public int maxProduct(int[] nums) {
int hi = nums[0], lo = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
int 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);
}
return best;
}
}