Maximum Product of First and Last Elements of a Subsequence

The most optimal solution achieves linear time complexity without using any extra space (O(1) space). We can combine the precomputation and the main calculation into a single pass. We use a two-pointer-like approach. One pointer j iterates from m-1 to the end of the array, representing the last element of the subsequence. Another pointer i_ptr tracks the end of the prefix from which the first element can be chosen. As j moves forward, i_ptr also moves forward, and we maintain the running minimum and maximum of the prefix ending at i_ptr. This way, we always have the necessary information to calculate the best product for each j without storing entire prefix arrays.

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.

class Solution {
    public long maximumProduct(int[] nums, int m) {
        int n = nums.length;
        // This logic correctly handles m=1, as j-i >= 0 means i<=j, and
        // max_{i<=j}(nums[i]*nums[j]) is equivalent to max_k(nums[k]*nums[k]).
        if (n < m) {
            return 0; // Or throw an exception for invalid input
        }

        long maxProduct = Long.MIN_VALUE;
        long prefixMax = nums[0];
        long prefixMin = nums[0];
        int i_ptr = 0;

        // Iterate j as the index of the last element
        for (int j = m - 1; j < n; j++) {
            // The first element's index `i` can be at most `j - m + 1`
            int i_limit = j - m + 1;

            // Update prefix min/max to cover the range up to i_limit
            // This inner loop runs disjointly over the course of the outer loop
            while (i_ptr < i_limit) {
                i_ptr++;
                prefixMax = Math.max(prefixMax, nums[i_ptr]);
                prefixMin = Math.min(prefixMin, nums[i_ptr]);
            }

            // Now prefixMax/prefixMin are the min/max of nums[0...i_limit]
            long currentVal = nums[j];
            long candidate1 = currentVal * prefixMax;
            long candidate2 = currentVal * prefixMin;

            maxProduct = Math.max(maxProduct, Math.max(candidate1, candidate2));
        }

        return maxProduct;
    }
}