LeetCode 2321. Maximum Score Of Spliced Array

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), s1 = 0, s2 = 0;
        vector<int> d(n + 1);
        for (int i = 0; i < n; ++i) {
            s1 += nums1[i], s2 += nums2[i];
            d[i + 1] = d[i] + nums1[i] - nums2[i]; // 前缀和数组记录两数组间的差值。
        }
        int ans = max(s1, s2), mind = 0, maxd = 0;
        for (int x : d) {
            ans = max(ans, s2 + (x - mind));
            ans = max(ans, s1 - (x - maxd));
            mind = min(mind, x);
            maxd = max(maxd, x);
        }
        return ans;
    }
};