Mảng con vòng tròn tổng tối đa trong C ++

Giả sử chúng ta có một mảng tròn C gồm các số nguyên được đại diện bởi A, chúng ta phải tìm tổng lớn nhất có thể có của một mảng con không rỗng của C. Ngoài ra, một mảng con chỉ có thể bao gồm mỗi phần tử của bộ đệm cố định A nhiều nhất một lần. Nếu mảng giống như [1, -2,3, -2], thì đầu ra sẽ là 3. Điều này là do mảng con [3] có tổng lớn nhất là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=kích thước của v
tạo mảng leftSum, leftSumMax, rightSum, rightSumMax tất cả có kích thước n
leftSum [0]:=v [0], leftSumMax [0]:=tối đa là 0 và v [0]
cho tôi trong phạm vi từ 1 đến n - 1
- leftSum [i]:=leftSum [i - 1] + v [i]
- leftSumMax [i]:=tối đa leftSum [i] và leftSumMax [i - 1]
rightSum [n - 1]:=v [n - 1], leftSumMax [n - 1]:=tối đa là 0 và v [n - 1]
đối với tôi trong phạm vi n - 2 xuống 0
- rightSum [i]:=rightSum [i + 1] + v [i]
- rightSumMax [i]:=tối đa rightSum [i + 1] và rightSum Max [i]
leftAns:=leftSum [0] + rightSumMax [1]
cho tôi trong phạm vi từ 1 đến n - 2
- leftAns:=tối đa leftAns, leftSum [i] + rightSumMax [i + 1]
rightAns:=rightSum [n - 1] + leftSumMax [n - 2]
đối với tôi trong phạm vi n - 2 xuống 1
- rightAns:=tối đa rightAns, rightSum [i] + leftSumMax [i - 1]
curr:=v [0], kadane:=v [0]
cho tôi trong phạm vi từ 1 đến n - 1
- curr:=max of v [1], curr + v [i]
- kadane:=max của curr và kadane
trả về giá trị tối đa của leftAns, rightAns và kadane

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[1,-2,3,-2]

Mảng con vòng tròn tổng tối đa trong C ++

Ví dụ

Đầu vào

Đầu ra