C++ 中三个不重叠子数组的最大和

假设我们有一个名为 nums 的正整数数组，我们需要找到三个不重叠的子数组，使得它们的和最大。这里每个子数组的大小都为 k，我们希望最大化所有 3*k 个元素的总和。

我们需要将结果表示为一个列表，其中包含每个区间的起始位置索引。如果有多个答案，我们将返回字典序最小的那个。

因此，如果输入类似于 [1,2,1,2,6,8,4,1] 且 k = 2，则结果将为 [0,3,5]，因此子数组 [1,2]、[2,6]、[8,4] 对应于起始索引 [0,3,5]。

为了解决这个问题，我们将遵循以下步骤：

  • n := nums 的大小
  • 定义一个大小为 3 的数组 ret，并将其填充为无穷大
  • 定义一个大小为 n + 1 的数组 sum
  • 对于初始化 i := 0，当 i < n 时，更新（i 增加 1），执行：
    • sum[i + 1] = sum[i] + nums[i]
  • 定义一个大小为 n 的数组 posLeft
  • 定义一个大小为 n 的数组 posRight，并将其填充为 n - k
  • 对于初始化 i := k，currMax := sum[k] - sum[0]，当 i < n 时，更新（i 增加 1），执行：
    • newTotal := sum[i + 1] - sum[i + 1 - k]
    • 如果 newTotal > currMax，则：
      • currMax := newTotal
      • posLeft[i] := i + 1 - k
    • 否则
      • posLeft[i] := posLeft[i - 1]
  • 对于初始化 i := n - k - 1，currMax := sum[n] - sum[n - k]，当 i >= 0 时，更新（i 减少 1），执行：
    • newTotal := sum[i + k] - sum[i]
    • 如果 newTotal >= currMax，则：
      • currMax := newTotal
      • posRight[i] := i
    • 否则
      • posRight[i] := posRight[i + 1]
  • req := 0
  • 对于初始化 i := k，当 i <= n - 2 * k 时，更新（i 增加 1），执行：
    • l := posLeft[i - 1], r := posRight[i + k]
    • temp := (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r])
    • 如果 temp > req，则：
      • ret[0] := l, ret[1] := i, ret[2] := r
      • req := temp
  • 返回 ret

让我们看看下面的实现，以便更好地理解：

示例

 实时演示

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
      int n = nums.size();
      vector <int> ret(3, INT_MAX);
      vector <int> sum(n + 1);
      for(int i = 0; i < n; i++){
         sum[i + 1] = sum[i] + nums[i];
      }
      vector <int> posLeft(n);
      vector <int> posRight(n, n - k);
      for(int i = k, currMax = sum[k] - sum[0]; i < n; i++){
         int newTotal = sum[i + 1] - sum[i + 1- k];
         if(newTotal > currMax){
            currMax = newTotal;
            posLeft[i] = i + 1 - k;
         }else{
            posLeft[i] = posLeft[i - 1];
         }
      }
      for(int i = n - k - 1, currMax = sum[n] - sum[n - k]; i >=0 ; i--){
         int newTotal = sum[i + k] - sum[i];
         if(newTotal >= currMax){
            currMax = newTotal;
            posRight[i] = i;
         }else{
            posRight[i] = posRight[i + 1];
         }
      }
      int req = 0;
      for(int i = k; i <= n - 2 * k; i++){
         int l = posLeft[i - 1];
         int r = posRight[i + k];
         int temp = (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r]);
         if(temp > req){
            ret[0] = l;
            ret[1] = i;
            ret[2] = r;
            req = temp;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1,2,6,8,4,1};
   print_vector(ob.maxSumOfThreeSubarrays(v, 2));
}

输入

{1,2,1,2,6,8,4,1}
2

输出

[0, 3, 5, ]

更新于: 2020年6月2日

125 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告