LeetCode Entry

1458. Max Dot Product of Two Subsequences

08.01.2026 hard 2026 kotlin rust

Max product of 2 subsequencies

1458. Max Dot Product of Two Subsequences hard blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1231

Problem TLDR

Max product of 2 subsequencies #hard #dp

Intuition

The solution is stable for every suffix (a[i..],b[j..]), memoize by the key of (i,j).

Approach

• use forward trick to not check the bounds dp[i+1]=dp[i]…
• use ‘stop here’ trick to handle negatives a[i]*b[j] + 0 instead of calling dfs(i+1,j+1)
• as we only accessing +-1, we can store just one recent row of dp instead of a full table

Complexity

• Time complexity: \(O(nm)\)

• Space complexity: \(O(m)\)

Code

// 17ms
    fun maxDotProduct(a: IntArray, b: IntArray): Int {
        val d = Array(2) { IntArray(b.size+1) { -1000000 }}
        for (i in a.indices) for (j in b.indices) d[(i+1)%2][j+1] =
            maxOf(d[(i+1)%2][j], d[i%2][j+1], a[i]*b[j], a[i]*b[j]+d[i%2][j])
        return d[a.size%2][b.size]
    }

// 0ms
    pub fn max_dot_product(a: Vec<i32>, b: Vec<i32>) -> i32 {
        let mut d = vec![vec![-1000000;b.len()+1];2];
        for i in 0..a.len() { for j in 0..b.len() {
            d[(i+1)&1][j+1] = d[(i+1)&1][j].max(d[i&1][j+1]).max(a[i]*b[j]).max(a[i]*b[j]+d[i&1][j])
        }} d[a.len()&1][b.len()]
    }