Maximum Product Subsequence of Exactly K Elements Using Dynamic Programming

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:

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.

Problem Statement

Example 1

Example 2

Approach

Why Do We Need min[j]?

Java Solution

Step-by-Step Explanation

1. Get the Array Size

2. Create the max and min Arrays

3. Why Use long?

4. The possible Array

5. Initialize the Product for Zero Elements

6. Traverse Every Array Element

7. Traverse j Backwards

8. Check Whether j - 1 Elements Are Possible

9. Calculate Both Possible Products

If num Is Positive

If num Is Negative

10. First Time Creating a Particular Size

11. Update the Existing Maximum

12. Update the Existing Minimum

13. Return the Answer

Dry Run

Why the Previous Greedy Approach Failed

Handling Zero

Why Do We Iterate Backwards?

Complexity

Key Takeaway

Why Do We Need `min[j]`?

2. Create the `max` and `min` Arrays

3. Why Use `long`?

4. The `possible` Array

7. Traverse `j` Backwards

8. Check Whether `j - 1` Elements Are Possible

If `num` Is Positive

If `num` Is Negative