3584.子序列首尾元素的最大乘积

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 nums 和一个整数 m。
返回任意大小为 m 的 子序列 中首尾元素乘积的最大值。
子序列 是可以通过删除原数组中的一些元素（或不删除任何元素），且不改变剩余元素顺序而得到的数组。
说明：

  • 1 <= nums.length <= 105

  • -105 <= nums[i] <= 105

  • 1 <= m <= nums.length
    示例：

  • 示例 1：

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

💻 解题思路

思路1：枚举右，维护左

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maximumProduct(self, nums: List[int], m: int) -> int:
        min_num = inf
        ans = max_num= -inf
        for right,num in enumerate(nums):
            if right < m-1:
                continue
            left = right - m +1
            min_num = min(nums[left],min_num)
            max_num = max(max_num,nums[left])
            ans = max(ans,min_num*num,max_num*num)
        return ans

思路1：📊 性能分析

复杂度验证
  • 时间复杂度：O(N)O(N)
  • 空间复杂度：O(1)O(1)