[LeetCode] 1458. Max Dot Product of Two Subsequences

給兩組數組陣列nums1及nums2，求其子序列(subsequence)之最大內積(dot product)。

原題連結：https://leetcode.com/problems/max-dot-product-of-two-subsequences/ 

看到題目有兩個重點：

1. 子序列(subsequence)：意思是從原本陣列中刪去一些元素所組成的陣列
2. 陣列中的元素有正有負

思路：因為要求最大內積，因此時間複雜度最小會是O(mn)，意思是在兩個陣列中所有的元素都會遍歷過一次。舉例來說：nums1=[2,1,-2,5]和nums2=[3,0,-6]可以建構成下列的表：

組成最大內積的兩個子序列是[2,-2]及[3,-6]，所以在表格中可以理解為：

在(i,j)以內的最大乘積總和。也就是說在(0,0)和(2,2)中最大的數字為6和12，其總和為18即為最大內積。

這就是經典的動態規劃題型(dynamic programming)，唯一要做的事情是我們要在二維表格中去維護dp[i][j]是在所有nums1[i]和nums2[j]小於i和j之子序列的最大內積。如下表：

因此，動態規劃的三個重點：

1. dp[i][j]是在(i,j)之內的子序列之最大內積
2. dp[i][j]的初始值：
1. dp[0][0] = nums1[0]*nums2[0] (題目要求子序列不可為empty)
2. dp[0][j]是nums1[0]*nums2[j]的最大值
3. dp[i][0]是nums1[i]*nums2[0]的最大值
3. 如何取得最大dp[i][j]：考慮五種狀況
1. dp[i-1][j-1]最大，不取nums1[i]*nums2[j]
2. dp[i][j-1]最大，不取nums1[i]*nums2[j]
3. dp[i-1][j]最大，不取nums1[i]*nums2[j]
4. dp[i-1][j-1]+nums1[i]*nums2[j]最大
5. nums1[i]*nums2[j]最大，不取之前的子序列內積

C++版本

int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
    vector<vector<int>> dp(nums1.size(), vector<int>(nums2.size()));
    dp[0][0] = nums1[0]*nums2[0]; // at least take nums1[0]*nums2[0]
    for (int i=1; i<nums1.size(); i++) {
        // current maximum of nums1[i]*nums2[0]
        dp[i][0] = max(nums1[i]*nums2[0], dp[i-1][0]);
    }
    for (int j=1; j<nums2.size(); j++) {
        // current maximum of nums1[0]*nums2[j]
        dp[0][j] = max(nums1[0]*nums2[j], dp[0][j-1]);
    }
    for (int i=1; i<nums1.size(); i++) {
        for (int j=1; j<nums2.size(); j++) {
            // dp[i][j] = maximum of all 5 cases
            int cur = nums1[i]*nums2[j];
            dp[i][j] = max(dp[i-1][j], max(dp[i][j-1], max(dp[i-1][j-1]+cur, max(cur, dp[i-1][j-1]))));  
        }
    }
    return dp[nums1.size()-1][nums2.size()-1];
}

Time Complexity: O(mn)

Space Complexity: O(mn)