C ++中的最大和圆子数组

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

假设我们有一个由A表示的整数的圆形数组C，我们必须找到C的一个非空子数组的最大和。而且，一个子数组最多只能包含固定缓冲区A的每个元素。如果数组类似于[1，-2,3，-2]，则输出将为3。这是因为subarray [3]的总和为3。

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

  • n：= v的大小

  • 创建所有大小为n的数组leftSum，leftSumMax，rightSum，rightSumMax

  • leftSum [0]：= v [0]，leftSumMax [0]：=最大值0和v [0]

  • 当我在1到n – 1的范围内时

    • leftSum [i]：= leftSum [i-1] + v [i]

    • leftSumMax [i]：= leftSum [i]和leftSumMax [i-1]的最大值

  • rightSum [n-1]：= v [n-1]，leftSumMax [n-1]：= 0和v [n-1]的最大值

  • 当我在n-2范围内降至0

    • rightSum [i]：= rightSum [i + 1] + v [i]

    • rightSumMax [i]：= rightSum [i + 1]和rightSum Max [i]的最大值

  • leftAns：= leftSum [0] + rightSumMax [1]

  • 当我在1到n – 2的范围内时

    • leftAns：= leftAns的最大值，leftSum [i] + rightSumMax [i +1]

  • rightAns：= rightSum [n-1] + leftSumMax [n-2]

  • 对于范围在n-2到1的i

    • rightAns：= rightAns的最大值，rightSum [i] + leftSumMax [i-1]

  • curr：= v [0]，kadane：= v [0]

  • 当我在1到n – 1的范围内时

    • curr：= v [1]的最大值，curr + v [i]

    • kadane：= curr和kadane的最大值

  • 返回leftAns，rightAns和kadane的最大值

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxSubarraySumCircular(vector<int>& v) {
      int n = v.size();
      vector <int> leftSum(n),leftSumMax(n),rightSum(n), rightSumMax(n);
      leftSum[0] = v[0];
      leftSumMax[0] = max((int)0,v[0]);
      for(int i =1;i<n;i++){
         leftSum[i] = leftSum[i-1] + v[i];
         leftSumMax[i] = max(leftSum[i],leftSumMax[i-1]);
      }
      rightSum[n-1] = v[n-1];
      rightSumMax[n-1] = max((int)0,v[n-1]);
      for(int i =n-2;i>=0;i--){
         rightSum[i] = rightSum[i+1]+v[i];
         rightSumMax[i] = max(rightSumMax[i+1],rightSum[i]);
      }
      int leftAns=leftSum[0]+rightSumMax[1];
      for(int i =1;i<n-1;i++){
         leftAns = max(leftAns,leftSum[i]+rightSumMax[i+1]);
      }
      int rightAns = rightSum[n-1]+leftSumMax[n-2];
      for(int i =n-2;i>=1;i--){
         rightAns = max(rightAns,rightSum[i]+leftSumMax[i-1]);
      }
      int curr=v[0];
      int kadane = v[0];
      for(int i =1;i<n;i++){
         curr = max(v[i],curr+v[i]);
         kadane = max(curr,kadane);
      }
      return max(leftAns,max(rightAns,kadane));
   }
};
main(){
   vector<int> v = {1,-2,3,-2};
   Solution ob;
   cout << (ob.maxSubarraySumCircular(v));
}

输入项

[1,-2,3,-2]

输出结果

3

以上是 C ++中的最大和圆子数组 的全部内容， 来源链接： utcz.com/z/338553.html

回到顶部