689. Maximum Sum of 3 Non-Overlapping Subarrays

dp 非典型 O(n) time O(n) space

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> w(n - k + 1);
        w[0] = accumulate(begin(nums), begin(nums) + k, 0);
        for (int i = 1; i < w.size(); ++i) {
            w[i] = w[i - 1] - nums[i - 1] + nums[i + k - 1];
        }
        vector<int> left(n - 3 * k + 1);
        for (int i = 0, best = i; i < left.size(); ++i) {
            if (w[i] > w[best]) {
                best = i;
            }
            left[i] = best;
        }
        vector<int> right(n - k + 1);
        for (int i = n - k, best = i; i >= 2 * k; --i) {
            if (w[i] >= w[best]) {
                best = i;
            }
            right[i] = best;
        }
        vector<int> res;
        for (int i = k, best = 0; i <= n - 2 * k; ++i) {
            int l = left[i - k], r = right[i + k];
            if (w[l] + w[i] + w[r] > best) {
                best = w[l] + w[i] + w[r];
                res = {l, i, r};
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> presum(n + 1); // 计算前缀和
        for (int i = 1; i <= n; ++i) {
            presum[i] = presum[i - 1] + nums[i - 1];
        }
        vector<int> w(n - k + 1); // 计算所有的相邻k个元素和
        for (int i = 0; i < w.size(); ++i) {
            w[i] = presum[i + k] - presum[i];
        }
        vector<int> left(n - 3 * k + 1); // 计算左边的所有下标使得对应下标开始的k元素和是到当前下标为止最大的
        int best = 0;
        for (int i = 0; i < left.size(); ++i) {
            if (w[i] > w[best]) {
                best = i;
            }
            left[i] = best; // best是全局最优，对每个left[i]记录当前全局最优值
        }
        vector<int> right(w.size()); // 因为用的是绝对下标，所以right数组的大小要和w保持一致
        best = w.size() - 1; // 右侧全局最优值从倒数第k个开始
        for (int i = w.size() - 1; i >= 0; --i) { // 这里一定要从右往左计算，因为我们只关心当前下标右侧的全局最优值
            if (w[i] >= w[best]) { // 这里一定要是>=因为我们要取字典序较小的下标，如果两个下标对应的k元素和相等，则取左侧较小的下标
                best = i;
            }
            right[i] = best;
        }
        int mx = 0;
        vector<int> res;
        for (int i = k; i < w.size() - k; ++i) { // 遍历中间的下标
            int l = left[i - k], r = right[i + k]; // 获取当前下标左侧和右侧的最优下标
            int sum = w[l] + w[i] + w[r]; // 查看三个下标对应的k元素和是否是整个数组最大和，是的话就更新
            if (sum > mx) {
                mx = sum;
                res = {l, i, r};
            }
        }
        return res;
    }
};

用这个

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = size(nums);
        vector<int> w(n);
        w[0] = accumulate(begin(nums), begin(nums) + k, 0);
        for (int i = 1; i + k <= n; ++i) {
            w[i] = w[i - 1] - nums[i - 1] + nums[i - 1 + k];
        }
        vector<int> left(n);
        int best = 0;
        for (int i = 1; i + k <= n; ++i) {
            if (w[i] > w[best]) {
                best = i;
            }
            left[i] = best;
        }
        vector<int> right(n);
        best = n - k;
        for (int i = n - k; i >= 0; --i) {
            if (w[i] >= w[best]) {
                best = i;
            }
            right[i] = best;
        }
        vector<int> res;
        best = 0;
        for (int i = k; i + k + k <= n; ++i) {
            int l = left[i - k], r = right[i + k];
            if (w[l] + w[i] + w[r] > best) {
                best = w[l] + w[i] + w[r];
                res = {l, i, r};
            }
        }
        return res;
    }
};