1458. Max Dot Product of Two Subsequences

/**
 * Problem: LeetCode 1458 - Max Dot Product of Two Subsequences
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n + 1][m + 1];

        // Initialize with a sufficiently small number that avoids integer underflow
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = -100_000_000;
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int prod = nums1[i - 1] * nums2[j - 1];
                int takeBoth = prod + Math.max(0, dp[i - 1][j - 1]);
                dp[i][j] = Math.max(takeBoth, Math.max(dp[i - 1][j], dp[i][j - 1]));
            }
        }

        return dp[n][m];
    }
}

"""
Problem: LeetCode 1458 - Max Dot Product of Two Subsequences
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)
        dp = [[float('-inf')] * (m + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                prod = nums1[i - 1] * nums2[j - 1]
                take_both = prod + max(0, dp[i - 1][j - 1])
                dp[i][j] = max(take_both, dp[i - 1][j], dp[i][j - 1])

        return int(dp[n][m])

/**
 * Problem: LeetCode 1458 - Max Dot Product of Two Subsequences
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        const int NEG_INF = -1e8;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, NEG_INF));

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                int prod = nums1[i - 1] * nums2[j - 1];
                int takeBoth = prod + max(0, dp[i - 1][j - 1]);
                dp[i][j] = max({takeBoth, dp[i - 1][j], dp[i][j - 1]});
            }
        }

        return dp[n][m];
    }
};

/**
 * Problem: LeetCode 1458 - Max Dot Product of Two Subsequences
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxDotProduct = function(nums1, nums2) {
    const n = nums1.length;
    const m = nums2.length;
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(-Infinity));

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            const prod = nums1[i - 1] * nums2[j - 1];
            const takeBoth = prod + Math.max(0, dp[i - 1][j - 1]);
            dp[i][j] = Math.max(takeBoth, dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[n][m];
};