845. Best Paired Dot Product
Two sensors record signed readings, a and b, over different time spans. An analyst wants to measure how strongly they agree by matching readings: she picks the same number (at least one) of readings from each list, keeping their original order, pairs the first picked reading of a with the first picked of b, the second with the second, and so on, then adds up the products of the pairs.
Return the largest total she can obtain. The picks must be non-empty, so when every product is negative the answer is the least negative single product.
Aim for time O(n * m) and extra space O(m), where n and m are the lengths of a and b.
Example 1
- Input:
- a = [3,-2,5], b = [-4,6,1]
- Output:
- 38
- Explanation:
Pairing -2 with -4 and then 5 with 6 gives 8 + 30 = 38, better than any other choice of matched positions.
Example 2
- Input:
- a = [-5,-3,-8], b = [4,7,2]
- Output:
- -6
- Explanation:
Every product is negative and you must pair at least one value, so the best single pair is -3 with 2 for -6.
Constraints
1 ≤ a.length, b.length ≤ 1000
-1000 ≤ a[i], b[j] ≤ 1000
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n * m)
- Space
- O(m)