3518. Maximum Multiplication Score¶

3518. Maximum Multiplication Score

Medium

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 i₀, i₁, i₂, and i₃ from the array b such that i₀ < i₁ < i₂ < i₃. Your score will be equal to the value a[0] * b[i₀] + a[1] * b[i₁] + a[2] * b[i₂] + a[3] * b[i₃].

Return the maximum score you can achieve.

Example 1:

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:

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⁵
-10⁵ <= a[i], b[i] <= 10⁵

Solution¶

class Solution {
    public long maxScore(int[] a, int[] b) {
        long dp[][] = new long[5][b.length + 1];
        for (long current[] : dp) Arrays.fill(current, -1);
        long res = solve(0 , 0 , a, b, dp);
        return res;
    }

    private long solve(int i , int j , int arr[] , int brr[], long dp[][]) {
        if (i >= arr.length) return 0;
        if (j >= brr.length) return Integer.MIN_VALUE;

        if (dp[i][j] != -1) return dp[i][j];

        long not_consider = solve(i , j + 1, arr, brr, dp);
        long consider = arr[i] * 1L * brr[j] + solve(i + 1, j + 1, arr, brr, dp);

        return dp[i][j] = Math.max(not_consider, consider);
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]