leetcode689. Maximum Sum of 3 Non-Overlapping Subarrays

た入场券 2022-05-31 23:18 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的子数组，并使取得的三个子数组总和最大。

#### **Solution One** ####

最简单的解法就是用三个循环从头到尾全遍历一遍，时间复杂度为O(n^3)，这个解法虽然没错，但很慢，在leetcode上跑回超时

class Solution {
    public:
        vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
            int i, j, h, s, tempsum;
            int size = nums.size();
            vector<int> sum;
            for (i = 0; i < size - k + 1; ++i) {
                s = 0;
                for (j = 0; j < k; ++j) {
                    s += nums[i + j];
                }
                sum.push_back(s);
            }
            vector<int> answer(3, 0);
            int maxsum = 0;
            for (i = 0; i < size - 3 * k + 1; ++i) {
                for (j = i + k; j < size - 2 * k + 1; ++j) {
                    for (h = j + k; h < size - k + 1; ++h) {
                        tempsum = sum[i] + sum[j] + sum[h];
                        if (tempsum > maxsum) {
                            maxsum = tempsum;
                            answer = {i,j,h};
                        }
                    }
                }
            }
            return answer;
        }
    };

#### **Solution Two** ####

进阶一点就是先固定中间的子数组地址 j，这样整个数组就被分成了左右两边，各取左右两边最大的那个作为另外两个子数组地址 i,h 就可以了，时间复杂度为O(n^2)，leetcode运行时间 557 ms

class Solution {
    public:
        vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
            int i, j, h, s = 0, tempsum;
            int size = nums.size();
            vector<int> sum;
            for (i = 0; i < size; ++i) {
                s += nums[i];
                if (i >= k)
                    s -= nums[i - k];
                if (i >= k - 1)
                    sum.push_back(s);
            }
            vector<int> answer(3, 0);
            int maxsum = 0;
            for (j = k; j < size - 2 * k + 1; ++j) {
                int maxi = 0, maxh = 0, maxsumi = 0, maxsumh = 0;
                for (i = 0; i < j - k + 1; ++i) {
                    if (sum[i] > maxsumi) {
                        maxi = i;
                        maxsumi = sum[i];
                    }
                }
                for (h = j + k; h < size - k + 1; ++h) {
                    if (sum[h] > maxsumh) {
                        maxh = h;
                        maxsumh = sum[h];
                    }
                }
                tempsum = sum[maxi] + sum[j] + sum[maxh];
                if (tempsum > maxsum) {
                    maxsum = tempsum;
                    answer = {maxi,j,maxh};
                }
            }
            return answer;
        }
    };

#### **Solution Three** ####

更进一步可以提前遍历一遍算好前n个或后n个子数组中的最大值，这样在解法二中 i,h 就可以直接取值而不用每次去求最大值了，时间复杂度为O(n)，leetcode运行时间 36 ms

class Solution {
    public:
        vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
            int i, j, h, s = 0, tempsum;
            int size = nums.size();
            vector<int> sum;
            for (i = 0; i < size; ++i) {
                s += nums[i];
                if (i >= k)
                    s -= nums[i - k];
                if (i >= k - 1)
                    sum.push_back(s);
            }
            int best = 0;
            vector<int> left(sum.size(), 0);
            for (i = 0; i < sum.size(); ++i) {
                if (sum[i] > sum[best])
                    best = i;
                left[i] = best;
            }
            best = sum.size() - 1;
            vector<int> right(sum.size(), 0);
            for (i = sum.size() - 1; i >= 0; --i) {
                if (sum[i] > sum[best])
                    best = i;
                right[i] = best;
            }
            vector<int> answer(3, 0);
            int maxsum = 0;
            for (j = k; j < size - 2 * k + 1; ++j) {
                tempsum = sum[left[j - k]] + sum[j] + sum[right[j + k]];
                if (tempsum > maxsum) {
                    maxsum = tempsum;
                    answer = {left[j-k],j,right[j+k]};
                }
            }
            return answer;
        }
    };