leetcode1458 Max Dot Product of Two Subsequences

 1 class Solution
 2 {
 3 public:
 4     int maxDotProduct(vector<int>& nums1, vector<int>& nums2)
 5     {
 6         int n = nums1.size(), m = nums2.size();
 7         vector<vector<int>> dp(n + 1, vector<int>(m + 1, -0x3f3f3f3f));
 8         for (int i = n - 1; i >= 0; i--)
 9         {
10             for (int j = m - 1; j >= 0; j--)
11             {
12                 int tmp = dp[i + 1][j + 1] > 0 ? dp[i + 1][j + 1] : 0;
13                 dp[i][j] = nums1[i] * nums2[j] + tmp;
14                 dp[i][j] = max(dp[i][j], dp[i + 1][j]);
15                 dp[i][j] = max(dp[i][j], dp[i][j + 1]);
16             }
17         }
18         return dp[0][0];
19     }
20 }