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

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 '没有找出满足条件的子序列！')

运行实例一

pls input nums=[2,3,4,5]

pls input k=-2

pls input limit=130

生成的所有子序列： [[2], [3], [4], [5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5], [2, 3, 4, 5]]

子序列： [2]

[2]的交错和为：2，[2]的元素乘积为：2

子序列： [3]

[3]的交错和为：3，[3]的元素乘积为：3

子序列： [4]

[4]的交错和为：4，[4]的元素乘积为：4

子序列： [5]

[5]的交错和为：5，[5]的元素乘积为：5

子序列： [2, 3]

[2, 3]的交错和为：-1，[2, 3]的元素乘积为：6

子序列： [2, 4]

[2, 4]的交错和为：-2，[2, 4]的元素乘积为：8

子序列： [2, 5]

[2, 5]的交错和为：-3，[2, 5]的元素乘积为：10

子序列： [3, 4]

[3, 4]的交错和为：-1，[3, 4]的元素乘积为：12

子序列： [3, 5]

[3, 5]的交错和为：-2，[3, 5]的元素乘积为：15

子序列： [4, 5]

[4, 5]的交错和为：-1，[4, 5]的元素乘积为：20

子序列： [2, 3, 4]

[2, 3, 4]的交错和为：3，[2, 3, 4]的元素乘积为：24

子序列： [2, 3, 5]

[2, 3, 5]的交错和为：4，[2, 3, 5]的元素乘积为：30

子序列： [2, 4, 5]

[2, 4, 5]的交错和为：3，[2, 4, 5]的元素乘积为：40

子序列： [3, 4, 5]

[3, 4, 5]的交错和为：4，[3, 4, 5]的元素乘积为：60

子序列： [2, 3, 4, 5]

[2, 3, 4, 5]的交错和为：-2，[2, 3, 4, 5]的元素乘积为：120

最大乘积为：120

运行实例二

pls input nums=[3,4,5]

pls input k=-1

pls input limit=20

生成的所有子序列： [[3], [4], [5], [3, 4], [3, 5], [4, 5], [3, 4, 5]]

子序列： [3]

[3]的交错和为：3，[3]的元素乘积为：3

子序列： [4]

[4]的交错和为：4，[4]的元素乘积为：4

子序列： [5]

[5]的交错和为：5，[5]的元素乘积为：5

子序列： [3, 4]

[3, 4]的交错和为：-1，[3, 4]的元素乘积为：12

子序列： [3, 5]

[3, 5]的交错和为：-2，[3, 5]的元素乘积为：15

子序列： [4, 5]

[4, 5]的交错和为：-1，[4, 5]的元素乘积为：20

子序列： [3, 4, 5]

[3, 4, 5]的交错和为：4，[3, 4, 5]的元素乘积为：60

最大乘积为：20

运行实例三

pls input nums=[5,7,9]

pls input k=6

pls input limit=20

生成的所有子序列： [[5], [7], [9], [5, 7], [5, 9], [7, 9], [5, 7, 9]]

子序列： [5]

[5]的交错和为：5，[5]的元素乘积为：5

子序列： [7]

[7]的交错和为：7，[7]的元素乘积为：7

子序列： [9]

[9]的交错和为：9，[9]的元素乘积为：9

子序列： [5, 7]

[5, 7]的交错和为：-2，[5, 7]的元素乘积为：35

子序列： [5, 9]

[5, 9]的交错和为：-4，[5, 9]的元素乘积为：45

子序列： [7, 9]

[7, 9]的交错和为：-2，[7, 9]的元素乘积为：63

子序列： [5, 7, 9]

[5, 7, 9]的交错和为：7，[5, 7, 9]的元素乘积为：315

没有找出满足条件的子序列！

运行实例四

pls input nums=[6]

pls input k=6

pls input limit=30

生成的所有子序列： [[6]]

子序列： [6]

[6]的交错和为：6，[6]的元素乘积为：6

最大乘积为：6

在leetcode的问题中，涉及到排列组合问题的解决，主要包括这样一些：

1. 求一个列表的全排列问题
2. 求一个列表的所有子数组问题
3. 求一个列表n个元素中任取m个元素组成全排列的问题
4. 求一个列表所有子序列的问题

这些问题的解决基本上都用到了递归的方法，反复研究其解决过程，能够更深刻领会递归原理和对列表的处理。