3290. Maximum Multiplication Score

Posted on Edited on In

3290. Maximum Multiplication Score

Description

You are given an integer array a of size 4 and another integer array b of size at least 4.

You need to choose 4 indices i0, i1, i2, and i3 from the array b such that i0 < i1 < i2 < i3. Your score will be equal to the value a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3].

Return the maximum score you can achieve.

Example 1:

1
2
3
Input: a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]

Output: 26

Explanation:

We can choose the indices 0, 1, 2, and 5. The score will be 3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26.

Example 2:

1
2
3
Input: a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]

Output: -1

Explanation:

We can choose the indices 0, 1, 3, and 4. The score will be (-1) * (-5) + 4 * (-1) + 5 * (-2) + (-2) * (-4) = -1.

Constraints:

  • a.length == 4
  • 4 <= b.length <= 10^5
  • -10^5 <= a[i], b[i] <= 10^5

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int m_, n_;

    // the meaning of dp[i][j]: when we are at ith item in a, and jth item in b
    // the maximum number we can achieve
    // the state transition:
    //  at jth item of a, we can either match or not
    vector<vector<long long>> dp;
    long long maxScore(vector<int>& a, vector<int>& b) {
        m_ = a.size(), n_ = b.size();
        dp.resize(m_, vector<long long>(n_, LONG_MIN));
        dp[0][0] = (long long)a[0] * b[0];
        for (int i = 0; i < m_; i++) {
            for (int j = i; j < n_ + i + 1 - m_; j++) {
                if (i) {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + (long long)a[i] * b[j]);
                } else if (j) {
                    dp[i][j] = max(dp[i][j - 1], (long long)a[i] * b[j]);
                }
            }
        }
        return dp[m_ - 1][n_ - 1];
    }
};

The intuitive way:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int m_, n_;

    // the meaning of dp[i][j]: when we are at ith item in a, and jth item in b
    // the maximum number we can achieve
    vector<array<long long, 4>> dp;
    long long maxScore(vector<int>& a, vector<int>& b) {
        m_ = a.size(), n_ = b.size();
        dp.resize(n_, array<long long, 4>({INT_MIN, INT_MIN, INT_MIN, INT_MIN}));
        long long res = dfs(0, 0, a, b);
        return res;
    }

    long long dfs(int i, int j, vector<int>& a, vector<int>& b) {
        if (i == m_ || j == n_) {
            return 0;
        }
        if (dp[j][i] != INT_MIN) {
            return dp[j][i];
        }
        long long res = LLONG_MIN;
        if (n_ - j > 4 - i) {
            res = dfs(i, j + 1, a, b);
        }
        res = max(res, dfs(i + 1, j + 1, a, b) + (long long)a[i] * b[j]);
        dp[j][i] = res;
        return res;
    }
};