1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <vector>

class Solution {
public:
    int maxDotProduct(std::vector<int>& nums1, std::vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        std::vector<int> dp(n + 1);
        
        for (int i = 0; i < m; ++i) {
            int tmp = 0, tmp2;
            for (int j = 0; j < n; ++j) {
                tmp2 = dp[j + 1];
                dp[j + 1] = std::max(dp[j], dp[j + 1]);
                dp[j + 1] = std::max(tmp + nums1[i] * nums2[j], dp[j + 1]);
                std::swap(tmp, tmp2);
            }
        }
        
        if (dp.back() == 0) {
            int a = 0x8000'0000, aa = 0x7fff'ffff;
            int b = 0x8000'0000, bb = 0x7fff'ffff;
            for (int num : nums1) {
                a = std::max(a, num);
                aa = std::min(aa, num);
            }
            for (int num : nums2) {
                b = std::max(b, num);
                bb = std::min(bb, num);
            }
            return std::max(a * bb, b * aa);
        }
        
        return dp.back();
    }
};