Maximum Score from Performing Multiplication Operations

// Accepted solution for LeetCode #1770: Maximum Score from Performing Multiplication Operations
class Solution {
    private Integer[][] f;
    private int[] multipliers;
    private int[] nums;
    private int n;
    private int m;

    public int maximumScore(int[] nums, int[] multipliers) {
        n = nums.length;
        m = multipliers.length;
        f = new Integer[m][m];
        this.nums = nums;
        this.multipliers = multipliers;
        return dfs(0, 0);
    }

    private int dfs(int i, int j) {
        if (i >= m || j >= m || (i + j) >= m) {
            return 0;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        int k = i + j;
        int a = dfs(i + 1, j) + nums[i] * multipliers[k];
        int b = dfs(i, j + 1) + nums[n - 1 - j] * multipliers[k];
        f[i][j] = Math.max(a, b);
        return f[i][j];
    }
}

// Accepted solution for LeetCode #1770: Maximum Score from Performing Multiplication Operations
func maximumScore(nums []int, multipliers []int) int {
	n, m := len(nums), len(multipliers)
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, m)
		for j := range f[i] {
			f[i][j] = 1 << 30
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= m || j >= m || i+j >= m {
			return 0
		}
		if f[i][j] != 1<<30 {
			return f[i][j]
		}
		k := i + j
		a := dfs(i+1, j) + nums[i]*multipliers[k]
		b := dfs(i, j+1) + nums[n-j-1]*multipliers[k]
		f[i][j] = max(a, b)
		return f[i][j]
	}
	return dfs(0, 0)
}

# Accepted solution for LeetCode #1770: Maximum Score from Performing Multiplication Operations
class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        @cache
        def f(i, j, k):
            if k >= m or i >= n or j < 0:
                return 0
            a = f(i + 1, j, k + 1) + nums[i] * multipliers[k]
            b = f(i, j - 1, k + 1) + nums[j] * multipliers[k]
            return max(a, b)

        n = len(nums)
        m = len(multipliers)
        return f(0, n - 1, 0)

// Accepted solution for LeetCode #1770: Maximum Score from Performing Multiplication Operations
/**
 * [1770] Maximum Score from Performing Multiplication Operations
 *
 * You are given two 0-indexed integer arrays nums and multipliers of size n and m respectively, where n >= m.
 * You begin with a score of 0. You want to perform exactly m operations. On the i^th operation (0-indexed) you will:
 *
 *     Choose one integer x from either the start or the end of the array nums.
 *     Add multipliers[i] * x to your score.
 *     
 *         Note that multipliers[0] corresponds to the first operation, multipliers[1] to the second operation, and so on.
 *     
 *     
 *     Remove x from nums.
 *
 * Return the maximum score after performing m operations.
 *  
 * Example 1:
 *
 * Input: nums = [1,2,3], multipliers = [3,2,1]
 * Output: 14
 * Explanation: An optimal solution is as follows:
 * - Choose from the end, [1,2,<u>3</u>], adding 3 * 3 = 9 to the score.
 * - Choose from the end, [1,<u>2</u>], adding 2 * 2 = 4 to the score.
 * - Choose from the end, [<u>1</u>], adding 1 * 1 = 1 to the score.
 * The total score is 9 + 4 + 1 = 14.
 * Example 2:
 *
 * Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
 * Output: 102
 * Explanation: An optimal solution is as follows:
 * - Choose from the start, [<u>-5</u>,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
 * - Choose from the start, [<u>-3</u>,-3,-2,7,1], adding -3 * -5 = 15 to the score.
 * - Choose from the start, [<u>-3</u>,-2,7,1], adding -3 * 3 = -9 to the score.
 * - Choose from the end, [-2,7,<u>1</u>], adding 1 * 4 = 4 to the score.
 * - Choose from the end, [-2,<u>7</u>], adding 7 * 6 = 42 to the score.
 * The total score is 50 + 15 - 9 + 4 + 42 = 102.
 *
 *  
 * Constraints:
 *
 * 	n == nums.length
 * 	m == multipliers.length
 * 	1 <= m <= 300
 * 	m <= n <= 10^5
 * 	-1000 <= nums[i], multipliers[i] <= 1000
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/
// discuss: https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    // Credit: https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/solutions/2455163/rust-bottom-up-and-top-down-dp-with-comments/
    pub fn maximum_score(nums: Vec<i32>, multipliers: Vec<i32>) -> i32 {
        let (n, m) = (nums.len(), multipliers.len());
        let mut dp = vec![vec![0; m + 1]; m + 1];

        for left in (0..m).rev() {
            for right in (0..m - left).rev() {
                let multiplier = multipliers[left + right];
                dp[left][right] = (dp[left + 1][right] + multiplier * nums[left])
                    .max(dp[left][right + 1] + multiplier * nums[n - right - 1]);
            }
        }

        dp[0][0]
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_1770_example_1() {
        let nums = vec![1, 2, 3];
        let multipliers = vec![3, 2, 1];

        let result = 14;

        assert_eq!(Solution::maximum_score(nums, multipliers), result);
    }

    #[test]
    fn test_1770_example_2() {
        let nums = vec![-5, -3, -3, -2, 7, 1];
        let multipliers = vec![-10, -5, 3, 4, 6];

        let result = 102;

        assert_eq!(Solution::maximum_score(nums, multipliers), result);
    }
}

// Accepted solution for LeetCode #1770: Maximum Score from Performing Multiplication Operations
function maximumScore(nums: number[], multipliers: number[]): number {
    const inf = 1 << 30;
    const n = nums.length;
    const m = multipliers.length;
    const f = new Array(m + 1).fill(0).map(() => new Array(m + 1).fill(-inf));
    f[0][0] = 0;
    let ans = -inf;
    for (let i = 0; i <= m; ++i) {
        for (let j = 0; j <= m - i; ++j) {
            const k = i + j - 1;
            if (i > 0) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j] + nums[i - 1] * multipliers[k]);
            }
            if (j > 0) {
                f[i][j] = Math.max(f[i][j], f[i][j - 1] + nums[n - j] * multipliers[k]);
            }
            if (i + j === m) {
                ans = Math.max(ans, f[i][j]);
            }
        }
    }
    return ans;
}