Max Multiplied Pairings Sequel - Google Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& nums, vector<int>& m) {
    if (m.empty()) return 0;
    if (m.size() == 1) return max(m[0] * nums.front(), m[0] * nums.back());
    int M = nums.size(), N = m.size(), ans = INT_MIN;
    vector<vector<int>> dp(N + 1, vector<int>(N + 1, INT_MIN));
    dp[1][0] = m[0] * nums.front();
    dp[0][1] = m[0] * nums.back();
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j <= i; j++) {
            int a = j == i ? INT_MIN : (dp[i - j - 1][j] + nums[i - j - 1] * m[i - 1]);
            int b = j == 0 ? INT_MIN : (dp[i - j][j - 1] + nums[M - j] * m[i - 1]);
            dp[i - j][j] = max(a, b);
            if (i == N) ans = max(ans, dp[i - j][j]);
        }
    }
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums, int[] multipliers) {
        if (nums == null || nums.length == 0)
            return 0;
        return getMax(
            nums, multipliers, 0, nums.length - 1, 0, multipliers.length - 1, new HashMap());
    }

    private int getMax(int[] nums, int[] mul, int low, int high, int idx, int high2,
        Map<String, Integer> memo_map) {
        if (idx == high2)
            return Math.max(nums[low] * mul[idx], nums[high] * mul[idx]);

        String str = new StringBuilder().append(low).append(high).append(idx).toString();
        if (memo_map.containsKey(str))
            return memo_map.get(str);

        int val1 =
            nums[low] * mul[idx] + getMax(nums, mul, low + 1, high, idx + 1, high2, memo_map);
        int val2 =
            nums[high] * mul[idx] + getMax(nums, mul, low, high - 1, idx + 1, high2, memo_map);

        memo_map.put(str, Math.max(val1, val2));
        return memo_map.get(str);
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums, mult):
        n, m = len(nums), len(mult)

        @functools.cache
        def go(i, j):
            if j == m:
                return 0
            return max(
                nums[i] * mult[j] + go(i + 1, j + 1), nums[n - j + i - 1] * mult[j] + go(i, j + 1)
            )

        return go(0, 0)