DSA-140 · Exact maximum/minimum ending-product state with sign reversals
Maximum Product Subarray
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 19549 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the largest product of any nonempty contiguous subarray of nums. The chosen elements must occupy one uninterrupted interval in original index order.
- nums is a non-null int[] of length 1..10000. Null throws NullPointerException; empty or oversized input throws IllegalArgumentException. Every signed int value, including MIN_VALUE and MAX_VALUE, is valid.
- Return an exact BigInteger with no overflow truncation or modulus, and preserve nums. A singleton returns its own value, including a negative value. An empty selection is forbidden, so ONE is not a default answer.
- Zeros are ordinary interval elements and may be the optimum. Negative values can turn the smallest ending product into the next largest product. Return only the optimum value, not interval indices; the quadratic interval baseline runs only on short tests.
Examples
Input:
nums=[2,3,-2,4]
Output:6The interval [2,3] beats every interval including the later negative.
Input:
nums=[-2,3,-4]
Output:24The minimum product ending before −4 is −6; multiplying it by −4 creates the maximum 24.
Input:
nums=[-2,0,-1]
Output:0The two negatives cannot be combined across the separating zero.
Input:
nums=[-2147483648,-1]
Output:2147483648The exact product exceeds int and must not wrap.
Before you start
- Contiguous subarrays versus arbitrary subsequences
- Order reversal under multiplication by a negative number
Recognize the structure
A contiguous interval ending at index i either starts at i or extends an interval ending exactly at i−1. Keeping only the previous maximum is insufficient because multiplying by a negative reverses order. Retain both the minimum and maximum ending products; they summarize the extremes of every possible extension. Keep a separate best over all endpoints to answer the global interval question.
Try before revealing
Hint 1
A contiguous interval ending here either starts here or extends one ending immediately before.
Hint 2
Which previous extreme becomes useful when the current value is negative?
Hint 3
Compare x, oldMaximum×x, and oldMinimum×x for both new extremes, then update a separate global best.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate every nonempty contiguous interval
For each start index, multiply successive values through every end index and maximize the exact product. The initial global best is an actual first element; each start uses ONE only as a temporary multiplication identity before consuming its first element. This makes O(n²) BigInteger-by-int multiplications and comparisons. Tests use bounded arrays for this method and a separate oracle that multiplies every interval with balanced grouping. Large all-equal inputs are checked against independently computed powers.
Improve the baseline
Define endpoint states rather than a global running product
H(i) is the largest product of any nonempty interval ending exactly at i, and L(i) is the smallest such product. Best(i) is the largest product of any interval inside the first i+1 occurrences. Seed all three from nums[0], so a negative singleton remains a valid negative answer.
List every possible ending interval
At value x=nums[i], a candidate interval is the singleton x or an earlier ending interval extended by x. For positive x, multiplication preserves order; for negative x it reverses order; for zero every extension becomes zero. Therefore the extremes of all extended products occur among old H×x and old L×x.
Compute both new extremes from the old pair
Set nextH=max(x,oldH×x,oldL×x) and nextL=min(x,oldH×x,oldL×x). Compute both multiplied candidates before assigning either endpoint state. Then update the global best with nextH. Multiplying the global best instead would incorrectly join intervals separated by gaps.
Handle sign changes, zeros, and restarts uniformly
For [-2,3,-4], endpoint pairs are (−2,−2), (3,−6), and (24,−12). A zero makes both ending states zero, while a later singleton can restart a better interval. No division by zero, special sign counter, or split-array mutation is needed.
Choose an exact numeric policy
Products of valid int entries can exceed even long, and MIN_VALUE×−1 is already unsafe in int. BigInteger.valueOf handles every input value exactly. Products grow with interval length, so a linear count of DP updates is not a constant-time arithmetic claim. The implementation performs two multiplications by a fixed-width int value per update.
Why it is correct
Nonempty base
The only interval ending at index zero is the first singleton. Seeding maximumEnding, minimumEnding, and best with that value establishes exact endpoint and global states without allowing an empty interval.
Extreme extension sufficiency
Every interval ending at i is either x alone or an old ending interval extended by x. Multiplication by x preserves or reverses the total ordering, or maps every product to zero. Thus old minimum and maximum attain both extremes of the extended family. Including x supplies every possible restart, so taking min/max of the three candidates is sound and complete.
Global optimum and termination
After computing the new maximum ending at i, any optimum in the larger prefix either ended earlier or ends now. Maximizing old best with nextMaximum covers both. Saved old candidates prevent within-iteration reuse. A finite increasing index loop terminates with the global optimum, with exact arithmetic and no input changes.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.math.BigInteger;
import java.util.Objects;
public final class Solution {
private Solution() {}
private static void validate(int[] nums) {
Objects.requireNonNull(nums, "nums");
if (nums.length == 0 || nums.length > 10_000) throw new IllegalArgumentException("length must be 1..10000");
}
public static BigInteger maxProduct(int[] nums) {
validate(nums);
BigInteger maximumEnding = BigInteger.valueOf(nums[0]);
BigInteger minimumEnding = maximumEnding, best = maximumEnding;
for (int index = 1; index < nums.length; index++) {
BigInteger value = BigInteger.valueOf(nums[index]);
BigInteger fromMaximum = maximumEnding.multiply(value);
BigInteger fromMinimum = minimumEnding.multiply(value);
BigInteger nextMaximum = value.max(fromMaximum).max(fromMinimum);
BigInteger nextMinimum = value.min(fromMaximum).min(fromMinimum);
maximumEnding = nextMaximum;
minimumEnding = nextMinimum;
best = best.max(maximumEnding);
}
return best;
}
// Baseline: all nonempty contiguous intervals; short inputs only.
public static BigInteger baseline(int[] nums) {
validate(nums);
BigInteger best = BigInteger.valueOf(nums[0]);
for (int start = 0; start < nums.length; start++) {
BigInteger product = BigInteger.ONE;
for (int end = start; end < nums.length; end++) {
product = product.multiply(BigInteger.valueOf(nums[end]));
best = best.max(product);
}
}
return best;
}
}
Read the meaningful blocks
Validate nonemptiness and initialize from data
Empty input is rejected rather than assigned zero or one. All signed ints are allowed, so there is no value scan or ad hoc sentinel. BigInteger initialization represents MIN_VALUE exactly.
Save both multiplied old extremes
fromMaximum and fromMinimum are computed before updating either live endpoint state. These immutable values preserve the old pair for both next min and next max comparisons.
Update endpoints and then the prefix best
The singleton participates in both extremes, enabling restart after an unfavorable prefix. best is a maximum across completed endpoint choices, not a product to extend. The returned immutable BigInteger can safely share the final optimum value.
Complexity
Let n be length and B the largest intermediate product bit length, at least one. The reference makes O(n) arithmetic operations, each multiplication having one fixed-width int operand. A conservative O(n(B+1)) bit-time bound and O(B+1) live auxiliary bits apply; B=O(n) because input magnitudes use at most 32 bits each. Thus linear updates can require quadratic worst-case bit work.
The interval baseline makes O(n²) arithmetic operations and uses O(B+1) live auxiliary bits; O(n²(B+1)) is a safe bit-time upper bound. Output needs up to O(B) bits. Neither algorithm materializes intervals or copies nums, and teaching histories are excluded from reference workspace.
Exact-state walkthroughs
Reveal normal and boundary traces
A previous minimum becomes the next maximum
Input: [-2,3,-4] · Exact maximum nonempty interval product: 24
Step 1 of 7: Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
Phase: initial.
Original contiguous positions
- 0: -2 — current
- 1: 3
- 2: -4
Live endpoint pair and global best
- maximum ending: -2
- minimum ending: -2
- global best: -2
A negative multiplier can turn the old minimum into the next maximum. Both multiplied candidates are saved before either state changes. The global best is compared with the new endpoint maximum; it is never multiplied across a gap.
Conceptual history — each row ends at one original index
Ending at 0
- maximum: -2
- minimum: -2
- best prefix: -2
Every interval is nonempty. A negative singleton remains negative, and a zero prevents combining separated negatives. BigInteger preserves exact products and its growing bit storage is part of complexity.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | [-2,3,-4] |
| phase | "initial" |
| maximumEnding | "-2" |
| minimumEnding | "-2" |
| best | "-2" |
| history | [{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"}] |
| index | 0 |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length == 0 || nums.length > 10_000) throw new IllegalArgumentException("length must be 1..10000"); 9 } 10 public static BigInteger maxProduct(int[] nums) { 11 validate(nums); 12 BigInteger maximumEnding = BigInteger.valueOf(nums[0]); 13 BigInteger minimumEnding = maximumEnding, best = maximumEnding; 14 for (int index = 1; index < nums.length; index++) { 15 BigInteger value = BigInteger.valueOf(nums[index]); 16 BigInteger fromMaximum = maximumEnding.multiply(value); 17 BigInteger fromMinimum = minimumEnding.multiply(value); 18 BigInteger nextMaximum = value.max(fromMaximum).max(fromMinimum); 19 BigInteger nextMinimum = value.min(fromMaximum).min(fromMinimum); 20 maximumEnding = nextMaximum; 21 minimumEnding = nextMinimum; 22 best = best.max(maximumEnding); 23 } 24 return best; 25 } 26 // Baseline: all nonempty contiguous intervals; short inputs only. 27 public static BigInteger baseline(int[] nums) { 28 validate(nums); 29 BigInteger best = BigInteger.valueOf(nums[0]); 30 for (int start = 0; start < nums.length; start++) { 31 BigInteger product = BigInteger.ONE; 32 for (int end = start; end < nums.length; end++) { 33 product = product.multiply(BigInteger.valueOf(nums[end])); 34 best = best.max(product); 35 } 36 } 37 return best; 38 } 39 } 40
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
- input
[-2,3,-4]- phase
"initial"- maximumEnding
"-2"- minimumEnding
"-2"- best
"-2"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"}]- index
0
- Compare restart and both old extreme extensions.
A negative multiplier reverses order, so old minimum may produce next maximum. Both multiplied candidates are saved before assigning either live state.
- input
[-2,3,-4]- phase
"candidate"- maximumEnding
"-2"- minimumEnding
"-2"- best
"-2"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"}]- index
1- value
"3"- fromMaximum
"-6"- fromMinimum
"-6"- nextMaximum
"3"- nextMinimum
"-6"
- Commit both endpoint extremes, then update the global prefix best.
Only an interval ending immediately before this index can be extended. The global best is compared, never multiplied across a gap.
- input
[-2,3,-4]- phase
"commit"- maximumEnding
"3"- minimumEnding
"-6"- best
"3"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"},{"index":1,"maximumEnding":"3","minimumEnding":"-6","best":"3"}]- index
1- value
"3"- fromMaximum
"-6"- fromMinimum
"-6"- nextMaximum
"3"- nextMinimum
"-6"
- Compare restart and both old extreme extensions.
A negative multiplier reverses order, so old minimum may produce next maximum. Both multiplied candidates are saved before assigning either live state.
- input
[-2,3,-4]- phase
"candidate"- maximumEnding
"3"- minimumEnding
"-6"- best
"3"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"},{"index":1,"maximumEnding":"3","minimumEnding":"-6","best":"3"}]- index
2- value
"-4"- fromMaximum
"-12"- fromMinimum
"24"- nextMaximum
"24"- nextMinimum
"-12"
- Commit both endpoint extremes, then update the global prefix best.
Only an interval ending immediately before this index can be extended. The global best is compared, never multiplied across a gap.
- input
[-2,3,-4]- phase
"commit"- maximumEnding
"24"- minimumEnding
"-12"- best
"24"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"},{"index":1,"maximumEnding":"3","minimumEnding":"-6","best":"3"},{"index":2,"maximumEnding":"24","minimumEnding":"-12","best":"24"}]- index
2- value
"-4"- fromMaximum
"-12"- fromMinimum
"24"- nextMaximum
"24"- nextMinimum
"-12"
- Return the exact best nonempty interval product.
Zeros and signs were handled by the same three candidates. History rows are explanatory; the Java reference retains only a constant number of BigInteger values.
- input
[-2,3,-4]- phase
"complete"- maximumEnding
"24"- minimumEnding
"-12"- best
"24"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"},{"index":1,"maximumEnding":"3","minimumEnding":"-6","best":"3"},{"index":2,"maximumEnding":"24","minimumEnding":"-12","best":"24"}]
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"24"
Zero prevents joining separated negatives
Input: [-2,0,-1] · Exact maximum nonempty interval product: 0
Step 1 of 7: Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
Phase: initial.
Original contiguous positions
- 0: -2 — current
- 1: 0
- 2: -1
Live endpoint pair and global best
- maximum ending: -2
- minimum ending: -2
- global best: -2
A negative multiplier can turn the old minimum into the next maximum. Both multiplied candidates are saved before either state changes. The global best is compared with the new endpoint maximum; it is never multiplied across a gap.
Conceptual history — each row ends at one original index
Ending at 0
- maximum: -2
- minimum: -2
- best prefix: -2
Every interval is nonempty. A negative singleton remains negative, and a zero prevents combining separated negatives. BigInteger preserves exact products and its growing bit storage is part of complexity.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | [-2,0,-1] |
| phase | "initial" |
| maximumEnding | "-2" |
| minimumEnding | "-2" |
| best | "-2" |
| history | [{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"}] |
| index | 0 |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length == 0 || nums.length > 10_000) throw new IllegalArgumentException("length must be 1..10000"); 9 } 10 public static BigInteger maxProduct(int[] nums) { 11 validate(nums); 12 BigInteger maximumEnding = BigInteger.valueOf(nums[0]); 13 BigInteger minimumEnding = maximumEnding, best = maximumEnding; 14 for (int index = 1; index < nums.length; index++) { 15 BigInteger value = BigInteger.valueOf(nums[index]); 16 BigInteger fromMaximum = maximumEnding.multiply(value); 17 BigInteger fromMinimum = minimumEnding.multiply(value); 18 BigInteger nextMaximum = value.max(fromMaximum).max(fromMinimum); 19 BigInteger nextMinimum = value.min(fromMaximum).min(fromMinimum); 20 maximumEnding = nextMaximum; 21 minimumEnding = nextMinimum; 22 best = best.max(maximumEnding); 23 } 24 return best; 25 } 26 // Baseline: all nonempty contiguous intervals; short inputs only. 27 public static BigInteger baseline(int[] nums) { 28 validate(nums); 29 BigInteger best = BigInteger.valueOf(nums[0]); 30 for (int start = 0; start < nums.length; start++) { 31 BigInteger product = BigInteger.ONE; 32 for (int end = start; end < nums.length; end++) { 33 product = product.multiply(BigInteger.valueOf(nums[end])); 34 best = best.max(product); 35 } 36 } 37 return best; 38 } 39 } 40
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
- input
[-2,0,-1]- phase
"initial"- maximumEnding
"-2"- minimumEnding
"-2"- best
"-2"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"}]- index
0
- Compare restart and both old extreme extensions.
A negative multiplier reverses order, so old minimum may produce next maximum. Both multiplied candidates are saved before assigning either live state.
- input
[-2,0,-1]- phase
"candidate"- maximumEnding
"-2"- minimumEnding
"-2"- best
"-2"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"}]- index
1- value
"0"- fromMaximum
"0"- fromMinimum
"0"- nextMaximum
"0"- nextMinimum
"0"
- Commit both endpoint extremes, then update the global prefix best.
Only an interval ending immediately before this index can be extended. The global best is compared, never multiplied across a gap.
- input
[-2,0,-1]- phase
"commit"- maximumEnding
"0"- minimumEnding
"0"- best
"0"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"},{"index":1,"maximumEnding":"0","minimumEnding":"0","best":"0"}]- index
1- value
"0"- fromMaximum
"0"- fromMinimum
"0"- nextMaximum
"0"- nextMinimum
"0"
- Compare restart and both old extreme extensions.
A negative multiplier reverses order, so old minimum may produce next maximum. Both multiplied candidates are saved before assigning either live state.
- input
[-2,0,-1]- phase
"candidate"- maximumEnding
"0"- minimumEnding
"0"- best
"0"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"},{"index":1,"maximumEnding":"0","minimumEnding":"0","best":"0"}]- index
2- value
"-1"- fromMaximum
"0"- fromMinimum
"0"- nextMaximum
"0"- nextMinimum
"-1"
- Commit both endpoint extremes, then update the global prefix best.
Only an interval ending immediately before this index can be extended. The global best is compared, never multiplied across a gap.
- input
[-2,0,-1]- phase
"commit"- maximumEnding
"0"- minimumEnding
"-1"- best
"0"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"},{"index":1,"maximumEnding":"0","minimumEnding":"0","best":"0"},{"index":2,"maximumEnding":"0","minimumEnding":"-1","best":"0"}]- index
2- value
"-1"- fromMaximum
"0"- fromMinimum
"0"- nextMaximum
"0"- nextMinimum
"-1"
- Return the exact best nonempty interval product.
Zeros and signs were handled by the same three candidates. History rows are explanatory; the Java reference retains only a constant number of BigInteger values.
- input
[-2,0,-1]- phase
"complete"- maximumEnding
"0"- minimumEnding
"-1"- best
"0"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"},{"index":1,"maximumEnding":"0","minimumEnding":"0","best":"0"},{"index":2,"maximumEnding":"0","minimumEnding":"-1","best":"0"}]
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"0"
A negative singleton remains negative
Input: [-2] · Exact maximum nonempty interval product: -2
Step 1 of 3: Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
Phase: initial.
Original contiguous positions
- 0: -2 — current
Live endpoint pair and global best
- maximum ending: -2
- minimum ending: -2
- global best: -2
A negative multiplier can turn the old minimum into the next maximum. Both multiplied candidates are saved before either state changes. The global best is compared with the new endpoint maximum; it is never multiplied across a gap.
Conceptual history — each row ends at one original index
Ending at 0
- maximum: -2
- minimum: -2
- best prefix: -2
Every interval is nonempty. A negative singleton remains negative, and a zero prevents combining separated negatives. BigInteger preserves exact products and its growing bit storage is part of complexity.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | [-2] |
| phase | "initial" |
| maximumEnding | "-2" |
| minimumEnding | "-2" |
| best | "-2" |
| history | [{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"}] |
| index | 0 |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length == 0 || nums.length > 10_000) throw new IllegalArgumentException("length must be 1..10000"); 9 } 10 public static BigInteger maxProduct(int[] nums) { 11 validate(nums); 12 BigInteger maximumEnding = BigInteger.valueOf(nums[0]); 13 BigInteger minimumEnding = maximumEnding, best = maximumEnding; 14 for (int index = 1; index < nums.length; index++) { 15 BigInteger value = BigInteger.valueOf(nums[index]); 16 BigInteger fromMaximum = maximumEnding.multiply(value); 17 BigInteger fromMinimum = minimumEnding.multiply(value); 18 BigInteger nextMaximum = value.max(fromMaximum).max(fromMinimum); 19 BigInteger nextMinimum = value.min(fromMaximum).min(fromMinimum); 20 maximumEnding = nextMaximum; 21 minimumEnding = nextMinimum; 22 best = best.max(maximumEnding); 23 } 24 return best; 25 } 26 // Baseline: all nonempty contiguous intervals; short inputs only. 27 public static BigInteger baseline(int[] nums) { 28 validate(nums); 29 BigInteger best = BigInteger.valueOf(nums[0]); 30 for (int start = 0; start < nums.length; start++) { 31 BigInteger product = BigInteger.ONE; 32 for (int end = start; end < nums.length; end++) { 33 product = product.multiply(BigInteger.valueOf(nums[end])); 34 best = best.max(product); 35 } 36 } 37 return best; 38 } 39 } 40
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
- input
[-2]- phase
"initial"- maximumEnding
"-2"- minimumEnding
"-2"- best
"-2"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"}]- index
0
- Return the exact best nonempty interval product.
Zeros and signs were handled by the same three candidates. History rows are explanatory; the Java reference retains only a constant number of BigInteger values.
- input
[-2]- phase
"complete"- maximumEnding
"-2"- minimumEnding
"-2"- best
"-2"- history
[{"index":0,"maximumEnding":"-2","minimumEnding":"-2","best":"-2"}]
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"-2"
Exact products beyond primitive ranges
Input: [2147483647,2147483647,2147483647] · Exact maximum nonempty interval product: 9903520300447984150353281023
Step 1 of 7: Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
Phase: initial.
Original contiguous positions
- 0: 2147483647 — current
- 1: 2147483647
- 2: 2147483647
Live endpoint pair and global best
- maximum ending: 2147483647
- minimum ending: 2147483647
- global best: 2147483647
A negative multiplier can turn the old minimum into the next maximum. Both multiplied candidates are saved before either state changes. The global best is compared with the new endpoint maximum; it is never multiplied across a gap.
Conceptual history — each row ends at one original index
Ending at 0
- maximum: 2147483647
- minimum: 2147483647
- best prefix: 2147483647
Every interval is nonempty. A negative singleton remains negative, and a zero prevents combining separated negatives. BigInteger preserves exact products and its growing bit storage is part of complexity.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | [2147483647,2147483647,2147483647] |
| phase | "initial" |
| maximumEnding | "2147483647" |
| minimumEnding | "2147483647" |
| best | "2147483647" |
| history | [{"index":0,"maximumEnding":"2147483647","minimumEnding":"2147483647","best":"2147483647"}] |
| index | 0 |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length == 0 || nums.length > 10_000) throw new IllegalArgumentException("length must be 1..10000"); 9 } 10 public static BigInteger maxProduct(int[] nums) { 11 validate(nums); 12 BigInteger maximumEnding = BigInteger.valueOf(nums[0]); 13 BigInteger minimumEnding = maximumEnding, best = maximumEnding; 14 for (int index = 1; index < nums.length; index++) { 15 BigInteger value = BigInteger.valueOf(nums[index]); 16 BigInteger fromMaximum = maximumEnding.multiply(value); 17 BigInteger fromMinimum = minimumEnding.multiply(value); 18 BigInteger nextMaximum = value.max(fromMaximum).max(fromMinimum); 19 BigInteger nextMinimum = value.min(fromMaximum).min(fromMinimum); 20 maximumEnding = nextMaximum; 21 minimumEnding = nextMinimum; 22 best = best.max(maximumEnding); 23 } 24 return best; 25 } 26 // Baseline: all nonempty contiguous intervals; short inputs only. 27 public static BigInteger baseline(int[] nums) { 28 validate(nums); 29 BigInteger best = BigInteger.valueOf(nums[0]); 30 for (int start = 0; start < nums.length; start++) { 31 BigInteger product = BigInteger.ONE; 32 for (int end = start; end < nums.length; end++) { 33 product = product.multiply(BigInteger.valueOf(nums[end])); 34 best = best.max(product); 35 } 36 } 37 return best; 38 } 39 } 40
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
- input
[2147483647,2147483647,2147483647]- phase
"initial"- maximumEnding
"2147483647"- minimumEnding
"2147483647"- best
"2147483647"- history
[{"index":0,"maximumEnding":"2147483647","minimumEnding":"2147483647","best":"2147483647"}]- index
0
- Compare restart and both old extreme extensions.
A negative multiplier reverses order, so old minimum may produce next maximum. Both multiplied candidates are saved before assigning either live state.
- input
[2147483647,2147483647,2147483647]- phase
"candidate"- maximumEnding
"2147483647"- minimumEnding
"2147483647"- best
"2147483647"- history
[{"index":0,"maximumEnding":"2147483647","minimumEnding":"2147483647","best":"2147483647"}]- index
1- value
"2147483647"- fromMaximum
"4611686014132420609"- fromMinimum
"4611686014132420609"- nextMaximum
"4611686014132420609"- nextMinimum
"2147483647"
- Commit both endpoint extremes, then update the global prefix best.
Only an interval ending immediately before this index can be extended. The global best is compared, never multiplied across a gap.
- input
[2147483647,2147483647,2147483647]- phase
"commit"- maximumEnding
"4611686014132420609"- minimumEnding
"2147483647"- best
"4611686014132420609"- history
[{"index":0,"maximumEnding":"2147483647","minimumEnding":"2147483647","best":"2147483647"},{"index":1,"maximumEnding":"4611686014132420609","minimumEnding":"2147483647","best":"4611686014132420609"}]- index
1- value
"2147483647"- fromMaximum
"4611686014132420609"- fromMinimum
"4611686014132420609"- nextMaximum
"4611686014132420609"- nextMinimum
"2147483647"
- Compare restart and both old extreme extensions.
A negative multiplier reverses order, so old minimum may produce next maximum. Both multiplied candidates are saved before assigning either live state.
- input
[2147483647,2147483647,2147483647]- phase
"candidate"- maximumEnding
"4611686014132420609"- minimumEnding
"2147483647"- best
"4611686014132420609"- history
[{"index":0,"maximumEnding":"2147483647","minimumEnding":"2147483647","best":"2147483647"},{"index":1,"maximumEnding":"4611686014132420609","minimumEnding":"2147483647","best":"4611686014132420609"}]- index
2- value
"2147483647"- fromMaximum
"9903520300447984150353281023"- fromMinimum
"4611686014132420609"- nextMaximum
"9903520300447984150353281023"- nextMinimum
"2147483647"
- Commit both endpoint extremes, then update the global prefix best.
Only an interval ending immediately before this index can be extended. The global best is compared, never multiplied across a gap.
- input
[2147483647,2147483647,2147483647]- phase
"commit"- maximumEnding
"9903520300447984150353281023"- minimumEnding
"2147483647"- best
"9903520300447984150353281023"- history
[{"index":0,"maximumEnding":"2147483647","minimumEnding":"2147483647","best":"2147483647"},{"index":1,"maximumEnding":"4611686014132420609","minimumEnding":"2147483647","best":"4611686014132420609"},{"index":2,"maximumEnding":"9903520300447984150353281023","minimumEnding":"2147483647","best":"9903520300447984150353281023"}]- index
2- value
"2147483647"- fromMaximum
"9903520300447984150353281023"- fromMinimum
"4611686014132420609"- nextMaximum
"9903520300447984150353281023"- nextMinimum
"2147483647"
- Return the exact best nonempty interval product.
Zeros and signs were handled by the same three candidates. History rows are explanatory; the Java reference retains only a constant number of BigInteger values.
- input
[2147483647,2147483647,2147483647]- phase
"complete"- maximumEnding
"9903520300447984150353281023"- minimumEnding
"2147483647"- best
"9903520300447984150353281023"- history
[{"index":0,"maximumEnding":"2147483647","minimumEnding":"2147483647","best":"2147483647"},{"index":1,"maximumEnding":"4611686014132420609","minimumEnding":"2147483647","best":"4611686014132420609"},{"index":2,"maximumEnding":"9903520300447984150353281023","minimumEnding":"2147483647","best":"9903520300447984150353281023"}]
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"9903520300447984150353281023"
Restart inside the array
Input: [2,3,-2,4] · Exact maximum nonempty interval product: 6
Step 1 of 9: Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
Phase: initial.
Original contiguous positions
- 0: 2 — current
- 1: 3
- 2: -2
- 3: 4
Live endpoint pair and global best
- maximum ending: 2
- minimum ending: 2
- global best: 2
A negative multiplier can turn the old minimum into the next maximum. Both multiplied candidates are saved before either state changes. The global best is compared with the new endpoint maximum; it is never multiplied across a gap.
Conceptual history — each row ends at one original index
Ending at 0
- maximum: 2
- minimum: 2
- best prefix: 2
Every interval is nonempty. A negative singleton remains negative, and a zero prevents combining separated negatives. BigInteger preserves exact products and its growing bit storage is part of complexity.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | [2,3,-2,4] |
| phase | "initial" |
| maximumEnding | "2" |
| minimumEnding | "2" |
| best | "2" |
| history | [{"index":0,"maximumEnding":"2","minimumEnding":"2","best":"2"}] |
| index | 0 |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(int[] nums) { 7 Objects.requireNonNull(nums, "nums"); 8 if (nums.length == 0 || nums.length > 10_000) throw new IllegalArgumentException("length must be 1..10000"); 9 } 10 public static BigInteger maxProduct(int[] nums) { 11 validate(nums); 12 BigInteger maximumEnding = BigInteger.valueOf(nums[0]); 13 BigInteger minimumEnding = maximumEnding, best = maximumEnding; 14 for (int index = 1; index < nums.length; index++) { 15 BigInteger value = BigInteger.valueOf(nums[index]); 16 BigInteger fromMaximum = maximumEnding.multiply(value); 17 BigInteger fromMinimum = minimumEnding.multiply(value); 18 BigInteger nextMaximum = value.max(fromMaximum).max(fromMinimum); 19 BigInteger nextMinimum = value.min(fromMaximum).min(fromMinimum); 20 maximumEnding = nextMaximum; 21 minimumEnding = nextMinimum; 22 best = best.max(maximumEnding); 23 } 24 return best; 25 } 26 // Baseline: all nonempty contiguous intervals; short inputs only. 27 public static BigInteger baseline(int[] nums) { 28 validate(nums); 29 BigInteger best = BigInteger.valueOf(nums[0]); 30 for (int start = 0; start < nums.length; start++) { 31 BigInteger product = BigInteger.ONE; 32 for (int end = start; end < nums.length; end++) { 33 product = product.multiply(BigInteger.valueOf(nums[end])); 34 best = best.max(product); 35 } 36 } 37 return best; 38 } 39 } 40
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed all nonempty interval states from the first occurrence.
The empty interval is forbidden, so a negative singleton must remain a negative answer. No primitive product is computed.
- input
[2,3,-2,4]- phase
"initial"- maximumEnding
"2"- minimumEnding
"2"- best
"2"- history
[{"index":0,"maximumEnding":"2","minimumEnding":"2","best":"2"}]- index
0
- Compare restart and both old extreme extensions.
A negative multiplier reverses order, so old minimum may produce next maximum. Both multiplied candidates are saved before assigning either live state.
- input
[2,3,-2,4]- phase
"candidate"- maximumEnding
"2"- minimumEnding
"2"- best
"2"- history
[{"index":0,"maximumEnding":"2","minimumEnding":"2","best":"2"}]- index
1- value
"3"- fromMaximum
"6"- fromMinimum
"6"- nextMaximum
"6"- nextMinimum
"3"
- Commit both endpoint extremes, then update the global prefix best.
Only an interval ending immediately before this index can be extended. The global best is compared, never multiplied across a gap.
- input
[2,3,-2,4]- phase
"commit"- maximumEnding
"6"- minimumEnding
"3"- best
"6"- history
[{"index":0,"maximumEnding":"2","minimumEnding":"2","best":"2"},{"index":1,"maximumEnding":"6","minimumEnding":"3","best":"6"}]- index
1- value
"3"- fromMaximum
"6"- fromMinimum
"6"- nextMaximum
"6"- nextMinimum
"3"
- Compare restart and both old extreme extensions.
A negative multiplier reverses order, so old minimum may produce next maximum. Both multiplied candidates are saved before assigning either live state.
- input
[2,3,-2,4]- phase
"candidate"- maximumEnding
"6"- minimumEnding
"3"- best
"6"- history
[{"index":0,"maximumEnding":"2","minimumEnding":"2","best":"2"},{"index":1,"maximumEnding":"6","minimumEnding":"3","best":"6"}]- index
2- value
"-2"- fromMaximum
"-12"- fromMinimum
"-6"- nextMaximum
"-2"- nextMinimum
"-12"
- Commit both endpoint extremes, then update the global prefix best.
Only an interval ending immediately before this index can be extended. The global best is compared, never multiplied across a gap.
- input
[2,3,-2,4]- phase
"commit"- maximumEnding
"-2"- minimumEnding
"-12"- best
"6"- history
[{"index":0,"maximumEnding":"2","minimumEnding":"2","best":"2"},{"index":1,"maximumEnding":"6","minimumEnding":"3","best":"6"},{"index":2,"maximumEnding":"-2","minimumEnding":"-12","best":"6"}]- index
2- value
"-2"- fromMaximum
"-12"- fromMinimum
"-6"- nextMaximum
"-2"- nextMinimum
"-12"
- Compare restart and both old extreme extensions.
A negative multiplier reverses order, so old minimum may produce next maximum. Both multiplied candidates are saved before assigning either live state.
- input
[2,3,-2,4]- phase
"candidate"- maximumEnding
"-2"- minimumEnding
"-12"- best
"6"- history
[{"index":0,"maximumEnding":"2","minimumEnding":"2","best":"2"},{"index":1,"maximumEnding":"6","minimumEnding":"3","best":"6"},{"index":2,"maximumEnding":"-2","minimumEnding":"-12","best":"6"}]- index
3- value
"4"- fromMaximum
"-8"- fromMinimum
"-48"- nextMaximum
"4"- nextMinimum
"-48"
- Commit both endpoint extremes, then update the global prefix best.
Only an interval ending immediately before this index can be extended. The global best is compared, never multiplied across a gap.
- input
[2,3,-2,4]- phase
"commit"- maximumEnding
"4"- minimumEnding
"-48"- best
"6"- history
[{"index":0,"maximumEnding":"2","minimumEnding":"2","best":"2"},{"index":1,"maximumEnding":"6","minimumEnding":"3","best":"6"},{"index":2,"maximumEnding":"-2","minimumEnding":"-12","best":"6"},{"index":3,"maximumEnding":"4","minimumEnding":"-48","best":"6"}]- index
3- value
"4"- fromMaximum
"-8"- fromMinimum
"-48"- nextMaximum
"4"- nextMinimum
"-48"
- Return the exact best nonempty interval product.
Zeros and signs were handled by the same three candidates. History rows are explanatory; the Java reference retains only a constant number of BigInteger values.
- input
[2,3,-2,4]- phase
"complete"- maximumEnding
"4"- minimumEnding
"-48"- best
"6"- history
[{"index":0,"maximumEnding":"2","minimumEnding":"2","best":"2"},{"index":1,"maximumEnding":"6","minimumEnding":"3","best":"6"},{"index":2,"maximumEnding":"-2","minimumEnding":"-12","best":"6"},{"index":3,"maximumEnding":"4","minimumEnding":"-48","best":"6"}]
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"6"
Test the contract
Input:
nums=[-2]
Output:-2No empty interval is allowed.
Input:
nums=[0]
Output:0Zero singleton.
Input:
nums=[-2,-3,-4]
Output:12The best interval need not include all entries.
Input:
nums=[0,-2,-3,0]
Output:6Restart and sign reversal around zeros.
Input:
nums=[2147483647,2147483647,2147483647]
Output:9903520300447984150353281023Three maximum-int values require exact arithmetic.
Input:
nums=[]
Output:IllegalArgumentExceptionNonempty contract.
Common mistakes and counterexamples
Track only the maximum ending product
Counterexample: [-2,3,-4] needs the old minimum −6 to discover 24.
Retain both endpoint extremes because negative multiplication reverses order.
Update the maximum before calculating the minimum
Counterexample: The second expression can accidentally use an already multiplied new state and reuse the current occurrence.
Compute both old-state products before assigning either endpoint state.
Allow an empty selection or combine separated negatives
Counterexample: [-2] must return −2, while [-2,0,-1] must not return two.
Seed from an actual singleton and extend only intervals ending immediately before the current index.
Use primitive multiplication or a blanket O(n)-time claim
Counterexample: MAX_VALUE repeated many times exceeds long, and exact products grow in bit length.
Use BigInteger and state both arithmetic-operation and bit-complexity bounds.
Follow-ups
Return one optimum interval.
Track start indices for the min/max endpoint candidates and store the winning global start/end on improvement. Define deterministic ties, such as shortest interval then earliest start. Preserve both old values and their identities until all next candidates are selected.
Require a bounded length or circular interval.
The current state merges intervals without retaining length or wrap information, so it cannot simply be reused. Define admissible interval identities, handle zeros and sign carefully, and derive a new bounded/circular algorithm. A global-product division shortcut is unsafe with zero and does not enforce interval constraints.
Use a primitive result with an overflow policy.
State whether all intermediate interval products are guaranteed to fit, whether overflow throws, or whether only the final answer is bounded. Math.multiplyExact can enforce checked arithmetic, but an intermediate overflow may occur even if a later zero makes the final optimum fit. Saturation or a modulus generally destroys the order comparisons required by this DP.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 136/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.