leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays 3个连续子数组最大和+动态规划DP

柔情只为你懂 2022-06-03 09:25 159阅读 0赞

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3\*k entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:  
Input: \[1,2,1,2,6,7,5,1\], 2  
Output: \[0, 3, 5\]  
Explanation: Subarrays \[1, 2\], \[2, 6\], \[7, 5\] correspond to the starting indices \[0, 3, 5\].  
We could have also taken \[2, 1\], but an answer of \[1, 3, 5\] would be lexicographically larger.  
Note:  
nums.length will be between 1 and 20000.  
nums\[i\] will be between 1 and 65535.  
k will be between 1 and floor(nums.length / 3).

本题题意很简单，就是找三个长度为k的子数组，要求这三个子数组之和最大，网上看到了一个简洁的解法，原因在于3的特殊性。什么是“三”，三就是左边一片，右边一片，中间一片。  
定义left数组，left\[i\]表示i左面最大的片段  
定义right数组，right\[i\]表示i右面最大的片段  
定义ans数组，ans\[i\]为中间一片、左边一片、右边一片之和，也就是ans\[i\]=s\[i\]+left\[i-k\]+right\[i+1\]

这是很棒的做法，时间复杂度是O(n)，很值得学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) 
        {
            int n = nums.size();
            vector<int> sum(n + 1, 0);
            vector<int> left(n, 0), right(n, n - k);
            for (int i = 1; i <= n; i++)
                sum[i] = sum[i - 1] + nums[i - 1];
    
            for (int i = k, one = sum[i] - sum[i - k]; i < n; i++)
            {
                if (sum[i + 1] - sum[i - k + 1] > one)
                {
                    one = sum[i + 1] - sum[i - k + 1];
                    left[i] = i - k + 1;
                }
                else
                    left[i] = left[i - 1];
            }
    
            for (int i = n - 1 - k, one = sum[n] - sum[n - k]; i >= 0; i--)
            {
                if (sum[i + k] - sum[i] > one)
                {
                    one = sum[i + k] - sum[i];
                    right[i] = i;
                }
                else
                    right[i] = right[i + 1];
            }
    
            vector<int> res(3, 0);
            int maxSum = 0;
            for (int i = k; i + 2*k <= n; i++)
            {
                int l = left[i - 1], r = right[i + k];
                int left = sum[l + k] - sum[l];
                int cen = sum[i + k] - sum[i];
                int right = sum[r + k] - sum[r];
                if (left + cen + right > maxSum)
                {
                    maxSum = left + cen + right;
                    res[0] = l;
                    res[1] = i;
                    res[2] = r;
                }
            }
            return res;
        }
    };