689. Maximum Sum of 3 Non-Overlapping Subarrays

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/

数组中找三个长度为K的无overlap且和最大的子数组。三个子数组把原数组分成了左，中和右三部分。设中间的子数组起始位置为i，那么左边子数组起始范围为[0, i - K]，右边子数组起始范围[i + K, N - 1]。因此用数组left依次记录以[0, i]范围内最大数组和的起始index，作为左边数组的备选；同理right记录[i, N - 1]范围内最大数组和的起始index，作为右边数组的备选。left和right的每个值用简单的DP可求得，然后再依次遍历i作为中间数组起始位置，调用left和right求得当前的最大和。

/*
 * @lc app=leetcode id=689 lang=cpp
 *
 * [689] Maximum Sum of 3 Non-Overlapping Subarrays
 */

// @lc code=start
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        const int N = nums.size();
        vector<int> sums(N + 1, 0), left(N, 0), right(N, N - k), res;
        for (int i = 1; i <= N; ++i) sums[i] = sums[i - 1] + nums[i - 1];
        for (int i = k, mx_sum = sums[k]; i < N; ++i) {
            if (sums[i + 1] - sums[i + 1 - k] > mx_sum) {
                left[i] = i + 1 - k;
                mx_sum = sums[i + 1] - sums[i + 1 - k];
            } else left[i] = left[i - 1];
        } 
        for (int i = N - k - 1, mx_sum = sums[N] - sums[N - k]; i >= 0; --i) {
            if (sums[i + k] - sums[i] >= mx_sum) {
                right[i] = i;
                mx_sum = sums[i + k] - sums[i];
            } else right[i] = right[i + 1];
        }
        for (int i = k, mx_sum = 0; i <= N - 2 * k; ++i) {
            const int l = left[i - 1], r = right[i + k], s = (sums[l + k] - sums[l]) + (sums[i + k] - sums[i]) + (sums[r + k] - sums[r]);
            if (s > mx_sum) {
                mx_sum = s;
                res = {l, i, r};
            }
        }
        return res;
    }
};
// @lc code=end