2022-04-09:给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ,其中 n >= m ,
数组下标 从 1 开始 计数。
初始时,你的分数为 0 。
你需要执行恰好 m 步操作。在第 i 步操作(从 1 开始 计数)中,需要:
选择数组 nums 开头处或者末尾处 的整数 x 。
你获得 multipliers[i] * x 分,并累加到你的分数中。
将 x 从数组 nums 中移除。
在执行 m 步操作后,返回 最大 分数。
力扣1770。
答案2022-04-09:
样本对应模型。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
nums := []int{-5, -3, -3, -2, 7, 1}
multipliers := []int{-10, -5, 3, 4, 6}
ret := maximumScore2(nums, multipliers)
fmt.Println(ret)
}
func maximumScore2(A, B []int) int {
if len(A) == 0 || len(B) == 0 || len(A) < len(B) {
return 0
}
N := len(A)
M := len(B)
dp := make([][]int, M+1)
for i := 0; i < M+1; i++ {
dp[i] = make([]int, M+1)
}
for L := M - 1; L >= 0; L-- {
for j := L + 1; j <= M; j++ {
R := N - M + j - 1
indexB := L + N - R - 1
dp[L][j] = getMax(A[L]*B[indexB]+dp[L+1][j], A[R]*B[indexB]+dp[L][j-1])
}
}
return dp[0][M]
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_01_1_week/Code03_MaximumScoreFromPerformingMultiplicationOperations.java)