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

解决leetcode第3836题.恰好k个下标对的最大得分

news 2026/3/26 17:31:03

3836.恰好K个下标对的最大得分

难度：困难

问题描述：

给你两个长度分别为n和m的整数数组nums1和nums2，以及一个整数k。

你必须恰好选择k对下标(i1,j1),(i2,j2),...,(ik,jk)，使得：

0<=i1<i2<...<ik<n

0<=j1<j2<...<jk<m

对于每对选择的下标(i,j)，你将获得nums1[i]*nums2[j]的得分。

总得分是所有选定下标对的乘积的总和。

返回一个整数，表示可以获得的最大总得分。

示例1:

输入：nums1=[1,3,2],nums2=[4,5,1],k=2

输出：22

解释：

一种最优的下标对选择方案是：

(i1,j1)=(1,0)，得分为3*4=12

(i2,j2)=(2,1)，得分为2*5=10

总得分为12+10=22。

示例2:

输入：nums1=[-2,0,5],nums2=[-3,4,-1,2],k=2

输出：26

解释：

一种最优的下标对选择方案是：

(i1,j1)=(0,0)，得分为-2*-3=6

(i2,j2)=(2,1)，得分为5*4=20

总得分为6+20=26。

示例3:

输入：nums1=[-3,-2],nums2=[1,2],k=2

输出：-7

解释：

最优的下标对选择方案是：

(i1,j1)=(0,0)，得分为-3*1=-3

(i2,j2)=(1,1)，得分为-2*2=-4

总得分为-3+(-4)=-7。

提示：

1<=n==nums1.length<=100

1<=m==nums2.length<=100

-106<=nums1[i],nums2[i]<=106

1<=k<=min(n,m)

问题分析：

因为从n个元素的数组中选k个元素，不好确定它们的顺序，所以采用从n个序列号中选k个序列号来处理，这样通过序列号既方便控制元素顺序，也方便提取原数组中的元素值。处理步骤如下：

先找到从n个元素的数组中取出k个元素的全排列方法，函数get_k_from_n(a,k)实现这一功能，其中参数a是包含n个序列号的数组，k为选取的个数
函数choose_subscript_array(n,k)通过调用get_k_from_n(a,k)实现从0至n-1的序列号中选取k个升序序列号的功能
将n和m及k传入choose_subscript_array(n,k)生成与nums1和nums2各自对应的序列号序列
主程序通过二重循环让与nums1和nums2对应的序列号配对，并计算得分，最后将其中最大得分输出，即为问题的解。

程序如下：

#从n个数中选择k个共有多少种选法 def get_k_from_n(a,k): n=len(a) if k==2: t=[] for i in range(n-1): for j in range (i+1,n): t.append([a[i],a[j]]) return t else: t=[] for i in range(n): left=a[:i] right=a[i+1:] temp=get_k_from_n(left+right,k-1) for j in temp: t.append([a[i]]+j) return t #从n个下标中生成k个下标序列并返回 def choose_subscript_array(n,k): a = list(range(n)) b = get_k_from_n(a, k) b = list(sorted(i) for i in b) t = [] for i in b: if i not in t: t.append(i) return t #主程序 nums1=eval(input('pls input nums1=')) nums2=eval(input('pls input nums2=')) k=int(input('pls input k=')) n=len(nums1) m=len(nums2) a=choose_subscript_array(n,k) b=choose_subscript_array(m,k) d_sum=0 for x in range(k): d_sum += nums1[a[0][x]] * nums2[b[0][x]] sum_max=d_sum sn=a[0] sm=b[0] for i in a: for j in b: d_sum = 0 for x in range(k): d_sum+=nums1[i[x]]*nums2[j[x]] if d_sum>sum_max: sum_max=d_sum sn=i sm=j print('最优的下标对选择方案是：') c=list(zip(sn,sm)) for i in range(k): print(f'(i{i}, j{i}) = {c[i]}，得分为 {nums1[c[i][0]]} *{nums2[c[i][1]]} ={nums1[c[i][0]] *nums2[c[i][1]]}') print(f'可以获得的最大总得分为{sum_max}')