🧮 Max Dot Product of Two Subsequences

Difficulty: 🔴 Hard
Topics: Dynamic Programming

📘 Problem Statement

You are given two integer arrays:

• nums1
• nums2

Your task is to return the maximum dot product between non-empty subsequences of nums1 and nums2 that have the same length.

🔍 Definition

🔹 Subsequence

A subsequence is formed by deleting zero or more elements from an array without changing the relative order of the remaining elements.

✅ Valid: [2,3,5] from [1,2,3,4,5]
❌ Invalid: [1,5,3]

✖️ Dot Product

For two arrays of equal length:

[a₁, a₂, ..., aₖ] · [b₁, b₂, ..., bₖ]
= a₁×b₁ + a₂×b₂ + ... + aₖ×bₖ

🧪 Examples

✅ Example 1

Input:
nums1 = [2,1,-2,5]
nums2 = [3,0,-6]

Output:
18

Explanation:
Choose subsequences [2, -2] and [3, -6]

(2 × 3) + (-2 × -6) = 6 + 12 = 18

✅ Example 2

Input:
nums1 = [3, -2]
nums2 = [2, -6, 7]

Output:
21

Explanation:
Choose subsequences [3] and [7]

3 × 7 = 21

⚠️ Example 3

Input:
nums1 = [-1, -1]
nums2 = [1, 1]

Output:
-1

Explanation:
Choose subsequences [-1] and [1]

-1 × 1 = -1

📏 Constraints

💡 Hint

This is a Dynamic Programming problem where handling negative values carefully is crucial.
A greedy approach will not work.

✨ Perfect problem to master DP with edge cases!