Best Paired Subsequence Product

Hard

You get two integer arrays first and second. Pick a non-empty subsequence from each (you may skip elements, but the rest keep their order), both of the same length. Then pair the elements up in order (first with first, second with second, and so on) and add up the products of the pairs. Return the largest value this sum can take.

Example 1

first=[4, -1, 2], second=[-3, 5] → 20

The best choice is a single pair: 4 from the first array and 5 from the second, 4 · 5 = 20. For instance, [-1, 2] with [-3, 5] gives only 3 + 10 = 13.

Example 2

first=[-2, -5], second=[3, 4] → -6

Every product is negative and an empty choice is not allowed, so take the least bad pair: -2 · 3 = -6.

Constraints

1 ≤ len(first), len(second) ≤ 500
-1000 ≤ first[i], second[i] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Water Between Walls Hard Biggest Solid Panel Block Hard Profit From Two Trades Hard Every Way to Space the Words Hard Crossing the Cave Hard

Input

first=[4, -1, 2], second=[-3, 5]

Expected

Run checks the first 3 tests in your browser. Submit checks all 111 tests on the server, hidden ones included.