Jan 8

LC-1458: Max Dot Product of Two Subsequences (Rust)

 Instead of trying every possible combination (which would be exponential), we use dynamic programming to build the solution step by step. At each step, we decide whether to include the current pair of elements or skip them.


You can build the solution gradually by considering one pair of elements at a time.
The secret is to realize that the optimal answer for the first i elements of nums1 and first j elements of nums2 depends on four simple choices at each step:
* Take just the current pair and start fresh
* Take the current pair and add it to what we had before
* Skip the current element from nums1
* Skip the current element from nums2

```
impl Solution {
    pub fn max_dot_product(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let (len_1, len_2) = (nums1.len(), nums2.len());
        let neg = -1_000_000_000;
        let mut dp = vec![vec![neg; len_2+1]; len_1+1];

        for i in 1..=len_1 {
            for j in 1..=len_2 {
                let take = nums1[i-1]*nums2[j-1] + dp[i-1][j-1].max(0);
                dp[i][j] = take.max(dp[i-1][j].max(dp[i][j-1]));
            }
        }
        dp[len_1][len_2]
    }
}
```