C ++中的最大和圆子数组
假设我们有一个由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]和rightSumMax[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