Problem Statement
Given an integer array arr[] and an integer k, find a subsequence of exactly k elements whose product is maximum.
Return the maximum product that can be obtained.
Example 1
Input:
arr[] = [1, 2, 0, 3]
k = 2
Output:
6
The subsequence {2, 3} gives:
2 × 3 = 6
Example 2
Input:
arr[] = [1, 2, -1, -3, -6, 4]
k = 4
Output:
144
The subsequence:
{2, -3, -6, 4}
gives:
2 × (-3) × (-6) × 4 = 144
Approach
The important difficulty in this problem is the presence of negative numbers.
When multiplying numbers, a negative value can change the result significantly.
For example:
(-5) × (-4) = 20
So two negative numbers can produce a positive product.
Also:
(-10) × (-2) = 20
Therefore, keeping only the maximum product is not enough.
We need to maintain both:
max[j] = maximum product possible using j elements
min[j] = minimum product possible using j elements
Why Do We Need min[j]?
Suppose:
min[j - 1] = -20
num = -5
Then:
(-20) × (-5) = 100
The minimum product can become the maximum product when multiplied by a negative number.
Therefore, for every subsequence size, we maintain both the maximum and minimum possible products.
Java Solution
class Solution {
public int maxProduct(int[] arr, int k) {
int n = arr.length;
long[] max = new long[k + 1];
long[] min = new long[k + 1];
boolean[] possible = new boolean[k + 1];
max[0] = 1;
min[0] = 1;
possible[0] = true;
for (int num : arr) {
for (int j = Math.min(k, n); j >= 1; j--) {
if (possible[j - 1]) {
long product1 = max[j - 1] * num;
long product2 = min[j - 1] * num;
if (!possible[j]) {
max[j] = Math.max(product1, product2);
min[j] = Math.min(product1, product2);
possible[j] = true;
} else {
max[j] = Math.max(max[j],
Math.max(product1, product2));
min[j] = Math.min(min[j],
Math.min(product1, product2));
}
}
}
}
return (int) max[k];
}
}
Step-by-Step Explanation
1. Get the Array Size
int n = arr.length;
This stores the number of elements in the array.
For example:
arr = [1, 2, -3, 4]
Then:
n = 4
2. Create the max and min Arrays
long[] max = new long[k + 1];
long[] min = new long[k + 1];
These arrays store the maximum and minimum products for different subsequence sizes.
For example, if:
k = 4
then:
max[0]
max[1]
max[2]
max[3]
max[4]
are available.
They represent:
max[1] → maximum product using 1 element
max[2] → maximum product using 2 elements
max[3] → maximum product using 3 elements
max[4] → maximum product using 4 elements
Similarly:
min[1]
min[2]
min[3]
min[4]
store the minimum products.
3. Why Use long?
long[] max
long[] min
Products can become larger than the normal int range in general versions of this problem.
Using long provides a larger range for intermediate calculations.
At the end:
return (int) max[k];
returns the required int result according to the given problem signature.
4. The possible Array
boolean[] possible = new boolean[k + 1];
This tells us whether it is possible to create a subsequence of a particular size.
Initially:
possible[0] = true;
because selecting zero elements is always possible.
All other values are initially:
false
5. Initialize the Product for Zero Elements
max[0] = 1;
min[0] = 1;
We use 1 because 1 is the multiplicative identity.
For example:
1 × 5 = 5
So when we select the first element:
max[0] * num
becomes:
1 × num = num
6. Traverse Every Array Element
for (int num : arr) {
This processes each element one by one.
For:
arr = [1, 2, -3, 4]
the loop processes:
num = 1
num = 2
num = -3
num = 4
7. Traverse j Backwards
for (int j = Math.min(k, n); j >= 1; j--) {
Here, j represents the number of elements selected.
The loop goes backwards.
This is very important because we are using one-dimensional DP arrays.
If we went forward, the current element could accidentally be used multiple times during the same iteration.
For example:
j = k
j = k - 1
j = k - 2
...
j = 1
Processing the states in reverse ensures that every array element is used at most once.
8. Check Whether j - 1 Elements Are Possible
if (possible[j - 1]) {
To create a subsequence containing j elements, we need to already have a valid subsequence containing j - 1 elements.
For example, to create a 3-element subsequence:
existing 2 elements + current element
Therefore:
possible[j - 1]
must be true.
9. Calculate Both Possible Products
long product1 = max[j - 1] * num;
long product2 = min[j - 1] * num;
This is the most important part of the solution.
We calculate the product using both:
maximum previous product
minimum previous product
Why?
Because the current number can be positive or negative.
If num Is Positive
A larger previous product generally gives a larger result.
If num Is Negative
A smaller negative previous product can produce a larger positive result.
For example:
max[j - 1] = -2
min[j - 1] = -10
num = -5
Then:
-2 × -5 = 10
-10 × -5 = 50
Therefore, the minimum previous product produces the maximum new product.
That is why both max and min are required.
10. First Time Creating a Particular Size
if (!possible[j]) {
If we have never created a subsequence of size j before, we directly initialize it.
max[j] = Math.max(product1, product2);
min[j] = Math.min(product1, product2);
possible[j] = true;
For example:
product1 = -10
product2 = 20
Then:
max[j] = 20
min[j] = -10
11. Update the Existing Maximum
If a subsequence of size j already exists:
max[j] = Math.max(max[j],
Math.max(product1, product2));
We compare:
old maximum
with:
new maximum
and keep the larger value.
12. Update the Existing Minimum
Similarly:
min[j] = Math.min(min[j],
Math.min(product1, product2));
We keep the smallest product.
This minimum is important because it can later become the maximum when multiplied by a negative number.
13. Return the Answer
return (int) max[k];
After processing the complete array:
max[k]
contains the maximum product possible using exactly k elements.
Therefore, we return it.
Dry Run
Consider:
arr = [-1, -2, -3, -4, -5]
k = 3
We need exactly 3 elements.
Some possible products are:
(-1) × (-2) × (-3) = -6
(-1) × (-2) × (-4) = -8
(-1) × (-2) × (-5) = -10
(-1) × (-3) × (-4) = -12
(-2) × (-3) × (-4) = -24
The maximum is:
-6
The algorithm correctly keeps track of both positive and negative intermediate products and finally obtains:
max[3] = -6
Therefore:
Output: -6
Why the Previous Greedy Approach Failed
A greedy approach that selects the best pair at every step does not always work.
For example:
arr = [-1, -2, -3, -4, -5]
k = 3
If we only compare pairs, we may select:
(-5) × (-4) = 20
But we still need one more element.
The resulting product could become:
20 × (-1) = -20
However, the correct answer is:
(-1) × (-2) × (-3) = -6
Since:
-6 > -20
the greedy pair selection fails.
The DP approach avoids this problem by considering both maximum and minimum products at every subsequence size.
Handling Zero
The solution also handles zero correctly.
For example:
arr = [-5, 0, 2]
k = 2
Possible products include:
(-5) × 0 = 0
0 × 2 = 0
(-5) × 2 = -10
The maximum is:
0
The DP naturally considers zero as a possible product.
Why Do We Iterate Backwards?
This line is important:
for (int j = Math.min(k, n); j >= 1; j--)
Suppose:
arr = [2]
k = 2
We must not use the same 2 twice.
If we iterate forward:
j = 1
j = 2
the value generated for j = 1 could immediately be used to generate j = 2, effectively using the same array element twice.
By iterating backwards:
j = 2
j = 1
we use the previous state before it can be modified by the current element.
Thus, each array element is selected at most once.
Complexity
The outer loop processes every element:
O(n)
The inner loop processes up to k states:
O(k)
Therefore:
Time Complexity: O(n × k)
The arrays have size k + 1:
Space Complexity: O(k)
Given the constraint:
n <= 30
this solution is efficient enough.
Key Takeaway
The main idea is:
For every subsequence size:
Keep the maximum product
Keep the minimum product
When processing a new number:
new maximum = max(max[j - 1] × num,
min[j - 1] × num)
new minimum = min(max[j - 1] × num,
min[j - 1] × num)
The reason we keep both values is that negative numbers can turn the minimum product into the maximum product.
This makes the solution work correctly for:
- Positive numbers
- Negative numbers
- Zero
- Odd
k - Even
k - All-negative arrays
- Mixed arrays
The final answer is stored in:
max[k]
and represents the maximum product obtainable from exactly k elements.
Join the conversation! Your thoughts help the community grow.