当前位置：首页 > article >正文

解决leetcode第3509题.最大化交错和为K的子序列乘积

article 2025/8/18 14:37:54

3509.最大化交错和为K的子序列乘积

难度：困难

问题描述：

给你一个整数数组nums和两个整数k与limit，你的任务是找到一个非空的子序列，满足以下条件：

它的交错和等于k。

在乘积不超过limit的前提下，最大化其所有数字的乘积。

返回满足条件的子序列的乘积。如果不存在这样的子序列，则返回-1。

子序列是指可以通过删除原数组中的某些（或不删除）元素并保持剩余元素顺序得到的新数组。

交错和是指一个从下标0开始的数组中，偶数下标的元素之和减去奇数下标的元素之和。

示例1：

输入：nums=[1,2,3],k=2,limit=10

输出：6

解释：

交错和为2的子序列有：

[1,2,3]

交错和：1-2+3=2

乘积：1*2*3=6

[2]

交错和：2

乘积：2

在limit内的最大乘积是6。

示例2：

输入：nums=[0,2,3],k=-5,limit=12

输出：-1

解释：

不存在交错和恰好为-5的子序列。

示例3：

输入：nums=[2,2,3,3],k=0,limit=9

输出：9

解释：

交错和为0的子序列包括：

[2,2]

交错和：2-2=0

乘积：2*2=4

[3,3]

交错和：3-3=0

乘积：3*3=9

[2,2,3,3]

交错和：2-2+3-3=0

乘积：2*2*3*3=36

子序列[2,2,3,3]虽然交错和为k且乘积最大，但36>9，超出limit。下一个最大且在limit范围内的乘积是9。

提示：

1<=nums.length<=150

0<=nums[i]<=12

-105<=k<=105

1<=limit<=5000

问题分析：

这个问题的关键是如何找出一个列表的所有子序列，又要用到递归的方法。在找出所有的子序列之后，遍历每一个子序列，计算其交错和及元素的乘积，检验其交错和是否等给定的k值，元素的乘积是否小于等于limit的值，最后将其中最大的元素乘积求出。

为此设计了这些函数：

计算交错和函数 get_interleaved_sum(a)

计算列表中元素乘积函数 get_product(a)

找到列表中所有元素的子序列函数 get_nonnull_subsequence(a)

从列表a中找出非空子序列的最大乘积函数 get_max_product_subsequence(a,k,limit)

程序如下：

#计算列表a的交错和并返回
def get_interleaved_sum(a):b=a[::2]c=a[1::2]return sum(b)-sum(c)#计算列表a的元素乘积并返回
def get_product(a):s=1for i in a:s*=ireturn s#找出列表a的所有子序列并返回
def get_nonnull_subsequence(a):n=len(a)if n==1:return [a]elif n==2:return [[a[0]],[a[1]],a]else:b=get_nonnull_subsequence(a[1:])d=[[a[0]]]d.extend(b)for i in b:c=[a[0]]+id.append(c)d.sort(key=lambda x:(len(x),x))return d#从列表a中找出具有最大乘积的非空子序列找返回
def get_max_product_subsequence(a,k,limit):a=get_nonnull_subsequence(a)print('生成的所有子序列：',a)s=0for i in a:print('子序列：',i)t=get_interleaved_sum(i)l=get_product(i)print(f'{i}的交错和为：{t}，{i}的元素乘积为：{l}')if t==k and s<l<=limit:s=lreturn -1 if s==0 else s#主程序
nums=eval(input('pls input nums='))
k=int(input('pls input k='))
limit=int(input('pls input limit='))
s=get_max_product_subsequence(nums,k,limit)
print(f'最大乘积为：{s}' if s!=-1 else '没有找出满足条件的子序列！')