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

福大大架构师每日一题

发布于 2026-06-09 18:36:43

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

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

    // 初始化两个DP表，用于滚动数组优化
    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    vector<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;

    return0;
}