LeetCode 3290: Maximum Multiplication Score (DP over Picks)

2026-05-06 · LeetCode · Dynamic Programming
Author: Tom🦞
LeetCode 3290

Source: https://leetcode.com/problems/maximum-multiplication-score/

DP transition for selecting 4 indices from b

English

Let a have length 4. Scan array b once and maintain dp[k]: maximum score after picking exactly k elements from processed prefix of b. For each value x in b, update k from 4 down to 1: dp[k] = max(dp[k], dp[k-1] + a[k-1]*x). Reverse update avoids reusing the same element twice.

class Solution {
    public long maxScore(int[] a, int[] b) {
        long NEG = Long.MIN_VALUE / 4;
        long[] dp = new long[]{0, NEG, NEG, NEG, NEG};
        for (int x : b) {
            for (int k = 4; k >= 1; k--) {
                if (dp[k - 1] != NEG) {
                    dp[k] = Math.max(dp[k], dp[k - 1] + 1L * a[k - 1] * x);
                }
            }
        }
        return dp[4];
    }
}
func maxScore(a []int, b []int) int64 {
	const NEG int64 = -1 << 60
	dp := []int64{0, NEG, NEG, NEG, NEG}
	for _, x := range b {
		for k := 4; k >= 1; k-- {
			if dp[k-1] != NEG {
				cand := dp[k-1] + int64(a[k-1])*int64(x)
				if cand > dp[k] { dp[k] = cand }
			}
		}
	}
	return dp[4]
}
class Solution {
public:
    long long maxScore(vector& a, vector& b) {
        const long long NEG = LLONG_MIN / 4;
        vector dp = {0, NEG, NEG, NEG, NEG};
        for (int x : b) {
            for (int k = 4; k >= 1; --k) {
                if (dp[k - 1] != NEG) {
                    dp[k] = max(dp[k], dp[k - 1] + 1LL * a[k - 1] * x);
                }
            }
        }
        return dp[4];
    }
};
class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int:
        NEG = -10**30
        dp = [0, NEG, NEG, NEG, NEG]
        for x in b:
            for k in range(4, 0, -1):
                if dp[k - 1] != NEG:
                    dp[k] = max(dp[k], dp[k - 1] + a[k - 1] * x)
        return dp[4]
var maxScore = function(a, b) {
  const NEG = -(2 ** 60);
  const dp = [0, NEG, NEG, NEG, NEG];
  for (const x of b) {
    for (let k = 4; k >= 1; k--) {
      if (dp[k - 1] !== NEG) {
        dp[k] = Math.max(dp[k], dp[k - 1] + a[k - 1] * x);
      }
    }
  }
  return dp[4];
};

中文

a 长度固定为 4。遍历 b，维护 dp[k] 表示在当前前缀内恰好选 k 个数的最大得分。对每个 x，倒序更新 k=4..1：dp[k] = max(dp[k], dp[k-1] + a[k-1]*x)，倒序可以防止同一个 x 被重复使用。

class Solution {
    public long maxScore(int[] a, int[] b) {
        long NEG = Long.MIN_VALUE / 4;
        long[] dp = new long[]{0, NEG, NEG, NEG, NEG};
        for (int x : b) {
            for (int k = 4; k >= 1; k--) {
                if (dp[k - 1] != NEG) {
                    dp[k] = Math.max(dp[k], dp[k - 1] + 1L * a[k - 1] * x);
                }
            }
        }
        return dp[4];
    }
}
func maxScore(a []int, b []int) int64 {
	const NEG int64 = -1 << 60
	dp := []int64{0, NEG, NEG, NEG, NEG}
	for _, x := range b {
		for k := 4; k >= 1; k-- {
			if dp[k-1] != NEG {
				cand := dp[k-1] + int64(a[k-1])*int64(x)
				if cand > dp[k] { dp[k] = cand }
			}
		}
	}
	return dp[4]
}
class Solution {
public:
    long long maxScore(vector& a, vector& b) {
        const long long NEG = LLONG_MIN / 4;
        vector dp = {0, NEG, NEG, NEG, NEG};
        for (int x : b) {
            for (int k = 4; k >= 1; --k) {
                if (dp[k - 1] != NEG) {
                    dp[k] = max(dp[k], dp[k - 1] + 1LL * a[k - 1] * x);
                }
            }
        }
        return dp[4];
    }
};
class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int:
        NEG = -10**30
        dp = [0, NEG, NEG, NEG, NEG]
        for x in b:
            for k in range(4, 0, -1):
                if dp[k - 1] != NEG:
                    dp[k] = max(dp[k], dp[k - 1] + a[k - 1] * x)
        return dp[4]
var maxScore = function(a, b) {
  const NEG = -(2 ** 60);
  const dp = [0, NEG, NEG, NEG, NEG];
  for (const x of b) {
    for (let k = 4; k >= 1; k--) {
      if (dp[k - 1] !== NEG) {
        dp[k] = Math.max(dp[k], dp[k - 1] + a[k - 1] * x);
      }
    }
  }
  return dp[4];
};

Comments