2025-04-21：最高乘法得分。用go语言，你有一个长度为4的整数数组a，还有一个长度不少于4的整数数组b。

需要从b中选择4个严格递增的下标i0、i1、i2和i3，使得i0 < i1 < i2 < i3。

你的目标是使表达式 a[0]*b[i0] + a[1]*b[i1] + a[2]*b[i2] + a[3]*b[i3] 的值达到最大。

请返回这个最大可能的得分。

a.length == 4。

4 <= b.length <= 100000。

-100000 <= a[i], b[i] <= 100000。

输入： a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]。

输出： 26。

解释：

选择下标 0, 1, 2 和 5。得分为 3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26。

题目来自leetcode3290。

详细步骤解析：

1. 初始化状态数组 f：

   • 创建长度为5的数组 f，表示当前已经选了 0 到 4 个元素的最大得分。

   • 初始时：

     • f[0] = 0，表示还没选任何 b 元素，得分为0。
     • f[1], f[2], f[3], f[4] 初始化为很小的负数（代码用 math.MinInt64 / 2 表示），表示对应状态还没有达到有效值。

2. 遍历数组 b 的元素：

   • 按顺序依次访问 b 中的每一个元素 y。

3. 状态转移：

   • 对每个 y，尝试更新 f 数组保存的状态。

   • 从后往前倒序遍历 j：3 → 2 → 1 → 0 ，对应着正在选择 a 中的第 j 个元素（从0开始计）。

     为什么倒序遍历？这样才能保证本次对 f[j+1] 的更新不会影响同一轮中 f[j] 的读取，避免状态覆盖错误。

   • 对于每个 j，尝试将 y 作为 a[j] 乘以的 b 元素，更新状态：

     f[j+1] = max(f[j+1], f[j] + a[j] * y)
     

     解释：

     • f[j] 是已经选择了 j 个元素时的最大得分。
     • 选择当前元素 y 担任第 j 个乘数对应的 b 元素后，得分增加 a[j] * y。
     • 于是 f[j+1] 就可以被更新为两者中的最大值。

4. 完成状态更新：

   • 当遍历完数组 b 所有元素后，f[4] 就是挑选完 4 个元素时能达到的最大得分。

5. 输出结果：

   • 返回 f[4] 即为答案。

时间复杂度分析

• 外层循环遍历 b 中所有元素，长度为 n。
• 内层循环从 j = 3 到 0，固定运行4次。
• 整体时间复杂度是：O(n * 4) = O(n)，其中 n 是 b 的长度。

额外空间复杂度分析

• 使用的辅助数组 f 长度为 5，大小固定。
• 不随输入大小增长，空间复杂度为 O(1)。

总结

• 通过动态规划维护状态数组 f，记录选中的个数对应的最大得分。
• 循环遍历 b 中元素，依次更新状态。
• 时间复杂度线性级别 O(n)。
• 空间复杂度常数级别 O(1)。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

func maxScore(a, b []int) int64 {
	f := [5]int64{}
	for j := 1; j < 5; j++ {
		f[j] = math.MinInt64 / 2
	}
	for _, y := range b {
		for j := 3; j >= 0; j-- {
			f[j+1] = max(f[j+1], f[j]+int64(a[j])*int64(y))
		}
	}
	return f[4]
}

func main() {
	a := []int{3, 2, 5, 6}
	b := []int{2, -6, 4, -5, -3, 2, -7}
	results := maxScore(a, b)
	fmt.Println(results)
}

Python完整代码如下：

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

def max_score(a, b):
    f = [float('-inf')] * 5
    f[0] = 0
    for y in b:
        for j in range(3, -1, -1):
            f[j+1] = max(f[j+1], f[j] + a[j] * y)
    return f[4]

if __name__ == "__main__":
    a = [3, 2, 5, 6]
    b = [2, -6, 4, -5, -3, 2, -7]
    result = max_score(a, b)
    print(result)