2025-11-29：子序列首尾元素的最大乘积。用go语言，给你一个整数数组 nums 和一个正整数 m。你需要从 nums 中按原有相对顺序挑出恰好 m 个元素（可以丢弃其它元素），在所有这样的长度为 m 的筛选结果中配资公司查询，计算每个序列第一个元素与最后一个元素的乘积，并返回这些乘积中的最大值。
1
-100000
1
输入： nums = [-1,-9,2,3,-2,-3,1], m = 1。
输出： 81。
解释：
子序列 [-9] 的首尾元素乘积最大：-9 * -9 = 81。因此，答案是 81。
题目来自力扣3584。
过程分步描述
1. 初始化变量：
• 将答案变量 ans 初始化为最小整数值（math.MinInt），用于记录遍历过程中找到的最大乘积。
• 初始化两个变量 mn 和 mx：
• mn（最小值跟踪器）初始化为最大整数值（math.MaxInt），用于记录当前可能作为子序列第一个元素的最小值。
• mx（最大值跟踪器）初始化为最小整数值（math.MinInt），用于记录当前可能作为子序列第一个元素的最大值。
• 这些初始化确保在首次比较时能被正确更新。
2. 遍历数组，枚举子序列的最后一个元素位置：
• 循环变量 i 从索引 m-1 开始，直到数组末尾（len(nums)-1）。这是因为子序列长度必须为 m，最后一个元素的索引至少为 m-1（索引从0开始）。
• 对于每个可能的最后一个元素位置 i：
a. 确定当前子序列第一个元素的候选范围：
• 对于固定的最后一个元素索引 i，第一个元素的索引 j 必须满足 j
b. 更新第一个元素候选值的最小值 mn 和最大值 mx：
• 获取当前第一个元素候选值 y = nums[i - m + 1]（即当前候选范围的最右端索引对应的元素）。
• 更新 mn = min(mn, y)，使 mn 始终记录从索引 0 到当前 i - m + 1 的所有可能第一个元素的最小值。
• 更新 mx = max(mx, y)，使 mx 始终记录同一范围内的最大值。
• 例如，当 i 增大时，mn 和 mx 会累积覆盖更多候选元素，动态维护全局最小和最大值。
c. 计算当前子序列的首尾乘积候选值：
• 获取当前最后一个元素的值 x = nums[i]。
• 计算两个关键乘积：
• 由于数组元素可能为负数，同时考虑最小值和最大值可以覆盖乘积最大化的场景（例如，两个负数相乘可能得正且很大）。
d. 更新全局最大乘积 ans：
• 将 ans 设置为当前 ans、x * mn 和 x * mx 中的最大值。
• 这确保在遍历过程中始终捕获所有可能子序列的首尾乘积最大值。
3. 返回结果：
• 循环结束后，将 ans 转换为 int64 类型并返回。如果没有任何满足条件的子序列（理论上不会发生，因为 m >= 1 且数组非空），ans 可能保持初始值，但题目保证有解。
时间和空间复杂度分析
• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。代码通过单次遍历数组（从 m-1 到 n-1），每个元素处理一次，操作均为常数时间（比较和算术运算）。枚举最后一个元素时，通过维护 mn 和 mx 避免了内部循环，高效覆盖所有可能第一个元素。
• 额外空间复杂度：O(1)。算法只使用了固定数量的整数变量（如 ans、mn、mx、循环索引等），不随输入规模 n 或 m 变化而占用额外空间。
关键点说明
• 有效性：代码利用动态维护极值的方法，避免了显式检查所有 O(n^2) 可能的子序列组合，显著优化了性能。对于每个最后一个元素，直接使用累积的 mn/mx 确定最佳第一个元素，无需嵌套循环。
• 处理负数：通过同时跟踪最小值和最大值，确保在元素含负数时也能正确计算最大乘积（例如，负数乘以负数可能得正）。
• 示例验证：以输入 nums = [-1, -9, 2, 3, -2, -3, 1], m = 1 为例，当 m=1 时，子序列仅含一个元素，首尾相同。代码遍历每个元素，计算其平方（即 x * x），并通过维护 mn/mx 捕获最大值 (-9)^2 = 81，与题目输出一致。
此方法高效且简洁，适用于大规模数组约束（n
Go完整代码如下：
package main
import (
"fmt"
"math"
)
func maximumProduct(nums []int, m int)int64 {
ans := math.MinInt
mn, mx := math.MaxInt, math.MinInt
for i := m - 1; i
// 维护左边 [0,i-m+1] 中的最小值和最大值
y := nums[i-m+1]
mn = min(mn, y)
mx = max(mx, y)
// 枚举右
x := nums[i]
ans = max(ans, x*mn, x*mx)
}
returnint64(ans)
}
func main {
nums := []int{-1, -9, 2, 3, -2, -3, 1}
m := 1
result := maximumProduct(nums, m)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def maximumProduct(nums, m):
if not nums or m len(nums):
return float('-inf')
max_product = float('-inf')
min_val = float('inf')
max_val = float('-inf')
for i in range(m - 1, len(nums)):
# 更新左侧窗口的最小值和最大值
left_val = nums[i - m + 1]
min_val = min(min_val, left_val)
max_val = max(max_val, left_val)
# 计算当前窗口右端点与最小/最大值的乘积
right_val = nums[i]
current_max = max(right_val * min_val, right_val * max_val)
max_product = max(max_product, current_max)
return max_product
# 测试
if __name__ == "__main__":
test_cases = [
([-1, -9, 2, 3, -2, -3, 1], 1),
]
for nums, m in test_cases:
result = maximumProduct(nums, m)
print(f"nums: {nums}, m: {m} -> result: {result}")
C++完整代码如下：
#include
#include
#include
#include
using namespace std;
long long maximumProduct(vector& nums, int m) {
long long ans = LLONG_MIN;
int mn = INT_MAX, mx = INT_MIN;
for (int i = m - 1; i
// 维护左边 [0,i-m+1] 中的最小值和最大值
int y = nums[i - m + 1];
mn = min(mn, y);
mx = max(mx, y);
// 枚举右
int x = nums[i];
ans = max({ans, (long long)x * mn, (long long)x * mx});
}
return ans;
}
int main {
vector nums = {-1, -9, 2, 3, -2, -3, 1};
int m = 1;
long long result = maximumProduct(nums, m);
cout
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
欢迎关注“福大大架构师每日一题”配资公司查询，发消息可获得面试资料，让AI助力您的未来发展。
新宝配资提示：文章来自网络，不代表本站观点。
