Medium

题目描述

给你一个整数数组 nums 和一个整数 m。

返回任意长度为 m 的 nums 子序列的首尾元素乘积的最大值。

示例 1：

输入：nums = [-1,-9,2,3,-2,-3,1], m = 1
输出：81
解释：子序列 [-9] 的首尾元素乘积最大：-9 * -9 = 81。因此答案是 81。

示例 2：

输入：nums = [1,3,-5,5,6,-4], m = 3
输出：20
解释：子序列 [-5, 6, -4] 的首尾元素乘积最大。

示例 3：

输入：nums = [2,-1,2,-6,5,2,-5,7], m = 2
输出：35
解释：子序列 [5, 7] 的首尾元素乘积最大。

约束条件：

  • 1 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5
  • 1 <= m <= nums.length

提示：

  • 我们可以选择 nums[i] 作为子序列的第一个元素，最后一个元素可以是 nums[i + m - 1], nums[i + m], ..., nums[n - 1] 中的任何一个。
  • 如果我们从最大的 i 开始选择第一个元素，后缀会变长，我们可以动态更新最小值和最大值。

解题思路

这道题要求找到长度为 m 的子序列中首尾元素乘积的最大值。

核心思路：

  1. 对于每个可能的起始位置 i，我们需要在位置 i + m - 1 到 n - 1 之间选择一个元素作为末尾元素
  2. 由于乘积可能为负数，我们需要同时维护后缀的最大值和最小值
  3. 从右到左遍历，对于每个起始位置，计算与后缀最大值和最小值的乘积，取最大者

算法步骤：

  1. 从右到左遍历数组，维护从当前位置到末尾的最大值和最小值
  2. 对于每个有效的起始位置 i（即 i <= n - m），计算 nums[i] 与后缀最大值、最小值的乘积
  3. 由于 nums[i] 可能为负数，所以 nums[i] * 后缀最小值 也可能产生最大乘积
  4. 更新全局最大值

这种方法的优势是只需要一次遍历，时间复杂度为 O(n)。

代码实现

class Solution {
public:
    long long maximumProduct(vector<int>& nums, int m) {
        int n = nums.size();
        long long maxProduct = LLONG_MIN;
        
        long long suffixMax = nums[n - 1];
        long long suffixMin = nums[n - 1];
        
        for (int i = n - m; i >= 0; i--) {
            if (i < n - 1) {
                long long newMax = max({(long long)nums[i + 1], suffixMax, suffixMin});
                long long newMin = min({(long long)nums[i + 1], suffixMax, suffixMin});
                suffixMax = newMax;
                suffixMin = newMin;
            }
            
            long long product1 = (long long)nums[i] * suffixMax;
            long long product2 = (long long)nums[i] * suffixMin;
            maxProduct = max(maxProduct, max(product1, product2));
        }
        
        return maxProduct;
    }
};

class Solution:
    def maximumProduct(self, nums: List[int], m: int) -> int:
        n = len(nums)
        max_product = float('-inf')
        
        suffix_max = nums[n - 1]
        suffix_min = nums[n - 1]
        
        for i in range(n - m, -1, -1):
            if i < n - 1:
                new_max = max(nums[i + 1], suffix_max, suffix_min)
                new_min = min(nums[i + 1], suffix_max, suffix_min)
                suffix_max = new_max
                suffix_min = new_min
            
            product1 = nums[i] * suffix_max
            product2 = nums[i] * suffix_min
            max_product = max(max_product, product1, product2)
        
        return max_product

public class Solution {
    public long MaximumProduct(int[] nums, int m) {
        int n = nums.Length;
        long maxProduct = long.MinValue;
        
        long suffixMax = nums[n - 1];
        long suffixMin = nums[n - 1];
        
        for (int i = n - m; i >= 0; i--) {
            if (i < n - 1) {
                long newMax = Math.Max(Math.Max((long)nums[i + 1], suffixMax), suffixMin);
                long newMin = Math.Min(Math.Min((long)nums[i + 1], suffixMax), suffixMin);
                suffixMax = newMax;
                suffixMin = newMin;
            }
            
            long product1 = (long)nums[i] * suffixMax;
            long product2 = (long)nums[i] * suffixMin;
            maxProduct = Math.Max(maxProduct, Math.Max(product1, product2));
        }
        
        return maxProduct;
    }
}

var maximumProduct = function(nums, m) {
    const n = nums.length;
    let maxProduct = -Infinity;
    
    let suffixMax = nums[n - 1];
    let suffixMin = nums[n - 1];
    
    for (let i = n - m; i >= 0; i--) {
        if (i < n - 1) {
            const newMax = Math.max(nums[i + 1], suffixMax, suffixMin);
            const newMin = Math.min(nums[i + 1], suffixMax, suffixMin);
            suffixMax = newMax;
            suffixMin = newMin;
        }
        
        const product1 = nums[i] * suffixMax;
        const product2 = nums[i] * suffixMin;
        maxProduct = Math.max(maxProduct, product1, product2);
    }
    
    return maxProduct;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)只需要一次从右到左的遍历
空间复杂度O(1)只使用常数个变量存储后缀最大值和最小值