Max Product Subsequence of Size K

Problem Overview

After sorting, the best size-k product comes from extremes: large positives on the right and large-magnitude negatives on the left.

Intuition

After sorting, the best size-k product comes from extremes: large positives on the right and large-magnitude negatives on the left. For even counts, greedily take the better end pair each time. Odd k needs one extra positive (or the least-bad negatives if everything is non-positive).

Algorithm

1Sort the array ascending.
2If k equals n, multiply everything.
3If the max is non-positive and k is odd, multiply the k rightmost values.
4If k is odd otherwise, take the largest value and reduce k by one.
5While k remains, compare the product of the two leftmost vs two rightmost and keep the larger pair.

Example Walkthrough

Input: arr = [-4, -2, 3, 5], k = 3

1. Odd k: take 5 first, then need two more.
2. Left pair (-4)*(-2)=8 beats right pair of what remains.
3. Product is 5 * 8 = 40.

Output: 40

Common Pitfalls

• Two negatives can beat two positives; always compare pair products.
• All-negative odd k must stay negative, so prefer smaller absolute values.
• Use long for intermediate products before casting back.
• Sorting is required; order in the original array does not matter for subsequences here.

Max Product Subsequence of Size K.java

Java

// Approach: Sort, then greedily take end pairs. Odd k: take the largest first
// so the rest is even. Each step compare product of two leftmost vs two
// rightmost and keep the larger pair. Special-case all-negative with odd k
// (pick least-magnitude negatives from the right).
// Complexity: O(n log n) time and O(1) extra space.
import java.util.*;

class Solution {

    public int maxProduct(int[] arr, int k) {
        int n = arr.length;
        Arrays.sort(arr);

        if (k == n) {
            long prod = 1;
            for (int x : arr) {
                prod *= x;
            }
            return (int) prod;
        }

        // All non-positive and odd k: product stays negative; take k largest
        // (least magnitude) from the right.
        if (arr[n - 1] <= 0 && (k & 1) == 1) {
            long prod = 1;
            for (int i = n - 1; i >= n - k; i--) {
                prod *= arr[i];
            }
            return (int) prod;
        }

        int left = 0;
        int right = n - 1;
        long maxProd = 1;

        if ((k & 1) == 1) {
            maxProd *= arr[right--];
            k--;
        }

        while (k > 0) {
            long leftPair = (long) arr[left] * arr[left + 1];
            long rightPair = (long) arr[right] * arr[right - 1];
            if (leftPair > rightPair) {
                maxProd *= leftPair;
                left += 2;
            } else {
                maxProd *= rightPair;
                right -= 2;
            }
            k -= 2;
        }

        return (int) maxProd;
    }
}

Was this solution helpful?