Maximum Product of First and Last Elements of a Subsequence

This approach builds upon the logic of the prefix array method but eliminates the need for extra space by computing the prefix information on-the-fly.

1. Initialize maxProduct to a very small value.
2. Initialize prefixMax and prefixMin to nums[0]. These will track the running min/max of the prefix relevant to the first element nums[i].
3. Initialize a pointer, i_ptr, to 0. This pointer marks the end of the prefix for which prefixMax and prefixMin have been calculated.
4. Iterate with a pointer j from m-1 to n-1. This j represents the index of the last element.
5. For each j, the maximum possible index for the first element i is i_limit = j - m + 1.
6. We need the min/max of the prefix nums[0...i_limit]. Since our i_ptr might be behind i_limit, we advance i_ptr up to i_limit, updating prefixMax and prefixMin with each new element encountered.
7. Once i_ptr equals i_limit, prefixMax and prefixMin hold the required values.
8. Calculate the candidate product using nums[j] with both prefixMax and prefixMin.
9. Update the global maxProduct with the larger of these candidates.
10. After the loop over j finishes, maxProduct holds the result.

This approach refines the prefix array method to use constant extra space. Instead of pre-calculating and storing all prefix minimums and maximums in an array, we can calculate them as needed during a single pass.

We iterate through the possible last element indices j from m-1 to n-1. For each j, the first element nums[i] can be chosen from the prefix nums[0...j-m+1]. We can maintain the minimum and maximum of this prefix in two variables. As j increments, the prefix nums[0...j-m+1] grows by one element. We can update our running prefix min/max in O(1) amortized time. This is a form of a sliding window or two-pointer technique where one pointer j scans the array, and another pointer i_ptr defines the boundary of the prefix being considered.

This single-pass algorithm is optimal in both time and space.

1class Solution {2    public long maximumProduct(int[] nums, int m) {3        int n = nums.length;4        // This logic correctly handles m=1, as j-i >= 0 means i<=j, and5        // max_{i<=j}(nums[i]*nums[j]) is equivalent to max_k(nums[k]*nums[k]).6        if (n < m) {7            return 0; // Or throw an exception for invalid input8        }9 10        long maxProduct = Long.MIN_VALUE;11        long prefixMax = nums[0];12        long prefixMin = nums[0];13        int i_ptr = 0;14 15        // Iterate j as the index of the last element16        for (int j = m - 1; j < n; j++) {17            // The first element's index `i` can be at most `j - m + 1`18            int i_limit = j - m + 1;19 20            // Update prefix min/max to cover the range up to i_limit21            // This inner loop runs disjointly over the course of the outer loop22            while (i_ptr < i_limit) {23                i_ptr++;24                prefixMax = Math.max(prefixMax, nums[i_ptr]);25                prefixMin = Math.min(prefixMin, nums[i_ptr]);26            }27 28            // Now prefixMax/prefixMin are the min/max of nums[0...i_limit]29            long currentVal = nums[j];30            long candidate1 = currentVal * prefixMax;31            long candidate2 = currentVal * prefixMin;32 33            maxProduct = Math.max(maxProduct, Math.max(candidate1, candidate2));34        }35 36        return maxProduct;37    }38}

The brute-force approach systematically checks every possible pair of elements that could serve as the first and last elements of a valid subsequence.

1. Initialize a variable maxProduct to a very small number (e.g., Long.MIN_VALUE) to store the maximum product found.
2. Iterate through the array with an index i from 0 to nums.length - 1. This index i represents the position of the first element of the subsequence.
3. For each i, start a nested loop with an index j from i + m - 1 to nums.length - 1. This index j represents the position of the last element.
4. The condition j >= i + m - 1 ensures that there are at least m - 2 elements available between indices i and j to form a subsequence of size m.
5. Inside the inner loop, calculate the product of nums[i] and nums[j]. Use a long to prevent overflow.
6. Compare this product with maxProduct and update maxProduct if the current product is larger.
7. After the loops complete, maxProduct will hold the maximum possible product.

The core idea is to exhaustively search for the best pair of elements. We can select nums[i] as the first element and nums[j] as the last element of our subsequence. For this to be possible, we must be able to select m-2 additional elements from the original array that lie between nums[i] and nums[j]. The number of elements available between index i and j is j - i - 1. Thus, we must satisfy the condition j - i - 1 >= m - 2, which simplifies to j - i >= m - 1.

This leads to a simple algorithm where we iterate through all possible i and for each i, we iterate through all valid j's, compute the product, and update our answer.

1class Solution {2    public long maximumProduct(int[] nums, int m) {3        int n = nums.length;4        if (m == 1) {5            long maxProd = Long.MIN_VALUE;6            for (int num : nums) {7                maxProd = Math.max(maxProd, (long) num * num);8            }9            return maxProd;10        }11 12        long maxProduct = Long.MIN_VALUE;13        for (int i = 0; i <= n - m; i++) {14            for (int j = i + m - 1; j < n; j++) {15                long product = (long) nums[i] * nums[j];16                if (product > maxProduct) {17                    maxProduct = product;18                }19            }20        }21        return maxProduct;22    }23}

Note: The special handling for m=1 can be merged into the main logic, as j >= i + 1 - 1 becomes j >= i. However, separating it can make the logic for the main case m > 1 clearer.

This approach optimizes the search for the second element. Instead of a nested loop, we precompute information about the array to find the best partner for each element in linear time.

1. We can iterate through the array, fixing one element of the product pair, and then efficiently find the best possible second element.
2. Let's fix the last element nums[j] and iterate j from m-1 to n-1.
3. For a given nums[j], the first element nums[i] must be chosen from the subarray nums[0...k] where k = j - m + 1.
4. To maximize nums[i] * nums[j], we need either the maximum or minimum value from nums[0...k], depending on the sign of nums[j].
   • If nums[j] is positive, we need the maximum value in nums[0...k].
   • If nums[j] is negative, we need the minimum value in nums[0...k].
5. We can precompute two arrays, prefixMax and prefixMin, in O(N) time. prefixMax[k] stores the maximum value in nums[0...k], and prefixMin[k] stores the minimum.
6. With these precomputed arrays, we can iterate j from m-1 to n-1, find the best nums[i] in O(1) time, calculate the product, and update the overall maximum product.

The problem is to maximize nums[i] * nums[j] subject to j - i >= m - 1. Let's iterate through all possible indices j for the last element. For each j, the index i for the first element must satisfy i <= j - m + 1. To maximize the product nums[i] * nums[j], we need to find the optimal nums[i] from the prefix nums[0...j-m+1].

If nums[j] is positive, we should pick the largest possible nums[i]. If nums[j] is negative, we should pick the smallest possible nums[i] (most negative) to make the product positive and large.

This can be solved efficiently by pre-calculating the minimum and maximum values for all prefixes of the array.

1class Solution {2    public long maximumProduct(int[] nums, int m) {3        int n = nums.length;4        if (n < m) return 0; // Or handle as per problem spec for invalid input5 6        // The case m=1 is equivalent to finding max(num*num), which the general7        // logic below correctly handles as it becomes max(nums[i]*nums[j]) for i<=j.8 9        long[] prefixMax = new long[n];10        long[] prefixMin = new long[n];11 12        prefixMax[0] = nums[0];13        prefixMin[0] = nums[0];14        for (int i = 1; i < n; i++) {15            prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);16            prefixMin[i] = Math.min(prefixMin[i - 1], nums[i]);17        }18 19        long maxProduct = Long.MIN_VALUE;20 21        // Iterate through all possible last elements `nums[j]`22        for (int j = m - 1; j < n; j++) {23            // The first element `nums[i]` must be in the range nums[0...j-m+1]24            int i_limit = j - m + 1;25            long pMax = prefixMax[i_limit];26            long pMin = prefixMin[i_limit];27 28            long currentVal = nums[j];29            long candidate1 = currentVal * pMax;30            long candidate2 = currentVal * pMin;31 32            maxProduct = Math.max(maxProduct, Math.max(candidate1, candidate2));33        }34 35        return maxProduct;36    }37}

An alternative symmetric solution involves precomputing suffix min/max arrays and iterating i from 0 to n-m.