C ++中3个非重叠子数组的最大和

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个称为正整数的数组，我们必须找到三个具有最大和的非重叠子数组。在这里，每个子数组的大小为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用inf填充

  • 定义大小为n + 1的数组和

  • 对于初始化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），执行-

    • posLeft [i]：= posLeft [i-1]

    • currMax：= newTotal

    • posLeft [i]：= i +1-k

    • newTotal：= sum [i +1]-sum [i +1-k]

    • 如果newTotal> currMax，则-

    • 除此以外

    • 对于初始化i：= n-k-1，currMax：= sum [n]-sum [n-k]，当i> = 0时，更新（将i减1），-

      • posRight [i]：= posRight [i +1]

      • currMax：= newTotal

      • posRight [i]：= i

      • newTotal：= sum [i + k]-sum [i]

      • 如果newTotal> = currMax，则-

      • 除此以外

      • 要求：= 0

      • 对于初始化i：= k，当i <= n-2 * k时，更新（将i增加1），执行-

        • ret [0]：= l，ret [1]：= i，ret [2]：= r

        • req：=临时

        • l：= posLeft [i-1]，r：= posRight [i + k]

        • 温度：=（sum [l + k]-sum [l]）+（sum [i + k]-sum [i]）+（sum [r + k]-sum [r]）

        • 如果temp> req，则-

      • 返回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, ]

      以上是 C ++中3个非重叠子数组的最大和 的全部内容， 来源链接： utcz.com/z/321692.html

      回到顶部