2026-06-08：恰好 K 个下标对的最大得分。用go语言，给定两个整数数组 nums1（长度 n）和 nums2（长度 m），以及一个整数 k。你需要从两

2026-06-08：恰好 K 个下标对的最大得分。用go语言，给定两个整数数组 nums1（长度 n）和 nums2（长度 m），以及一个整数 k。你需要从两个数组中各选出 k 个下标对，满足下标对的顺序严格递增：

• 选中的下标对为 (i1, j1), (i2, j2), …, (ik, jk)

• 必须满足：0 ≤ i1 < i2 < … < ik < n，并且 0 ≤ j1 < j2 < … < jk < m

• 每选中一个下标对 (i, j)，就能得到分数 nums1[i] × nums2[j]

• 总分等于所有 k 个选择对应分数的加和

任务：求在满足上述条件的前提下，能够得到的最大总分是多少。

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

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

-1000000 <= nums1[i], nums2[i] <= 1000000。

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

输入： 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。

题目来自力扣3836。

一、分步骤详细执行过程

整个过程分为K轮循环（因为要选恰好K个下标对），每一轮对应「选第t个下标对」（t从1到K）。

步骤1：初始化准备

1. 创建两个大小为(n+1) × (m+1)的二维数组 f、g（n是nums1长度，m是nums2长度）。

2. 所有位置填充极小值（代表初始状态不可达）。

3. 第一轮循环开始，目标：计算选1个下标对的最大得分。

步骤2：第1轮循环（选第1个下标对，t=1）

这一轮要找到所有满足i₁ < n，j₁ < m的单个下标对，计算得分，保留最大值。

1.边界预处理
先把不合法的位置（无法选1个下标对的位置）标记为极小值，排除无效状态。

2.遍历所有合法的(i,j)
遍历nums1的每个位置i、nums2的每个位置j，满足：

• 选1个下标对，下标无递增约束（只要在数组内）

• 状态更新：g[i+1][j+1]取三种情况的最大值：
✅ 不选当前i：继承上方状态g[i][j+1]
✅ 不选当前j：继承左方状态g[i+1][j]
✅ 选当前(i,j)作为第1个下标对：nums1[i] * nums2[j]

3.数组交换
计算完成后，f和g交换，此时f数组存储了「选1个下标对」的所有最大得分。

对应示例：
选1个的最大得分是 3×5=15（i=1,j=1）。

步骤3：第2轮循环（选第2个下标对，t=2，直到K轮）

这是关键轮次，必须满足下标严格递增：i₂>i₁，j₂>j₁。

1.边界预处理
因为要选2个下标对，必须预留足够的后续元素，所以把无法选2个的位置标记为极小值。

2.遍历所有合法的(i,j)
遍历nums1和nums2的位置，严格满足：

• 当前i > 上一个选中的i₁

• 当前j > 上一个选中的j₁
状态更新规则：
g[i+1][j+1]= 最大值（不选i、不选j、选当前(i,j)）
选当前(i,j)时，得分 =上一轮f[i][j]（选1个的最大得分） + nums1[i]×nums2[j]

3.数组交换
交换后，f数组存储选2个下标对的最大得分。

对应示例：
上一轮选1个的最优是15，本轮找到组合：
选(1,0)得12 → 再选(2,1)得10 → 总分22，这就是全局最大值。

步骤4：循环结束，获取结果

完成K轮循环后，f[n][m]就是：
在nums1全部n个元素、nums2全部m个元素中，恰好选K个合法下标对的最大总分。
最后将结果转为int64返回。

二、时间复杂度分析

时间复杂度由三层循环决定：

1. 最外层：循环K次（选K个下标对）

2. 中间层：遍历nums1的所有元素，次数为n

3. 最内层：遍历nums2的所有元素，次数为m

总时间复杂度：O(K × n × m)

• 题目约束：n、m≤100，K≤100，计算量=100×100×100=1e6，完全满足运行要求。

三、额外空间复杂度分析

额外空间仅用于两个动态规划二维数组：

• f数组：(n+1) × (m+1)

• g数组：(n+1) × (m+1)

总额外空间复杂度：O(n × m)

• 没有使用其他递归栈、集合等额外空间，空间效率很高。

总结

1. 解题核心：滚动二维动态规划，用两个数组交替记录选t个下标对的最大得分；

2. 执行过程：分K轮循环，每轮计算选t个的最优解，严格保证下标递增；

3. 时间复杂度：O(K·n·m)，三层循环驱动；

4. 额外空间复杂度：O(n·m)，仅使用两个二维状态数组。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
)

 func maxScore(nums1, nums2 []int, K int)int64 {
    n, m := len(nums1), len(nums2)
    f := make([][]int, n+1)
    g := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, m+1)
        g[i] = make([]int, m+1)
    }
    for k := 1; k <= K; k++ {
        for j := k; j <= m-(K-k); j++ {
            g[k-1][j] = math.MinInt
        }
        for i := k - 1; i < n-(K-k); i++ { // 后面还要选 K-k 个下标对
            g[i+1][k-1] = math.MinInt
            for j := k - 1; j < m-(K-k); j++ {
                g[i+1][j+1] = max(g[i][j+1], g[i+1][j], f[i][j]+nums1[i]*nums2[j])
            }
        }
        f, g = g, f
    }
    returnint64(f[n][m])
}

 func main() {
    nums1 := []int{1, 3, 2}
    nums2 := []int{4, 5, 1}
    k := 2
    result := maxScore(nums1, nums2, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import math

 def maxScore(nums1, nums2, K):
    n, m = len(nums1), len(nums2)
    # 初始化两个DP表，用于滚动数组优化
    f = [[0] * (m + 1) for _ in range(n + 1)]
    g = [[0] * (m + 1) for _ in range(n + 1)]
    # 外循环：从1到K，表示已选择的对数
    for k in range(1, K + 1):
        # 初始化g表的边界条件
        for j in range(k, m - (K - k) + 1):
            g[k-1][j] = -math.inf
        for i in range(k - 1, n - (K - k)):
            g[i+1][k-1] = -math.inf
            for j in range(k - 1, m - (K - k)):
                g[i+1][j+1] = max(
                    g[i][j+1],
                    g[i+1][j],
                    f[i][j] + nums1[i] * nums2[j]
                )
        # 交换f和g，实现滚动数组
        f, g = g, f
    return f[n][m]

 def main():
    nums1 = [1, 3, 2]
    nums2 = [4, 5, 1]
    k = 2
    result = maxScore(nums1, nums2, k)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

    


 using namespace std;

 long long maxScore(vector& nums1, vector& nums2, int K) {
    int n = nums1.size();
    int m = nums2.size();

     // 初始化两个DP表，用于滚动数组优化
    vector 
 
 int 
 >> f(n +  
 1 
 , vector< 
 int 
 >(m +  
 1 
 )); 
 
 
     vector 
 
 int 
 >> g(n +  
 1 
 , vector< 
 int 
 >(m +  
 1 
 )); 
 
 
 
 
      
 // 外循环：从1到K，表示已选择的对数 
 
 
      
 for 
  ( 
 int 
  k =  
 1 
 ; k <= K; k++) { 
 
 
          
 // 初始化g表的边界条件 
 
 
          
 for 
  ( 
 int 
  j = k; j <= m - (K - k); j++) { 
 
 
             g[k 
 -1 
 ][j] = INT_MIN; 
 
 
         } 
 
 
 
 
          
 for 
  ( 
 int 
  i = k -  
 1 
 ; i < n - (K - k); i++) { 
 
 
             g[i+ 
 1 
 ][k 
 -1 
 ] = INT_MIN; 
 
 
              
 for 
  ( 
 int 
  j = k -  
 1 
 ; j < m - (K - k); j++) { 
 
 
                 g[i+ 
 1 
 ][j+ 
 1 
 ] = max({g[i][j+ 
 1 
 ], g[i+ 
 1 
 ][j], f[i][j] + nums1[i] * nums2[j]}); 
 
 
             } 
 
 
         } 
 
 
 
 
          
 // 交换f和g，实现滚动数组 
 
 
         swap(f, g); 
 
 
     } 
 
 
 
 
      
 return 
  (long long)f[n][m]; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > nums1 = { 
 1 
 ,  
 3 
 ,  
 2 
 }; 
 
 
     vector< 
 int 
 > nums2 = { 
 4 
 ,  
 5 
 ,  
 1 
 }; 
 
 
      
 int 
  k =  
 2 
 ; 
 
 
 
 
     long long result = maxScore(nums1, nums2, k); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。