C++ এ সর্বাধিক যোগফল সার্কুলার সাবারে

ধরুন আমাদের কাছে A দ্বারা উপস্থাপিত পূর্ণসংখ্যার একটি বৃত্তাকার অ্যারে C আছে, আমাদের C-এর একটি অ-খালি সাবয়ারের সর্বাধিক সম্ভাব্য যোগফল খুঁজে বের করতে হবে। এছাড়াও, একটি সাবয়ারে শুধুমাত্র নির্দিষ্ট বাফার A-এর প্রতিটি উপাদানকে সর্বাধিক একবারে অন্তর্ভুক্ত করতে পারে। যদি অ্যারেটি [1,-2,3,-2] এর মত হয়, তাহলে আউটপুট হবে 3। এর কারণ হল subarray[3]-এর সর্বোচ্চ যোগফল 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=v

  এর আকার

• লেফটসুম, লেফটসুম ম্যাক্স, রাইটসুম, রাইটসুমম্যাক্স সমস্ত আকারের অ্যারে তৈরি করুন n

• leftSum[0] :=v[0], leftSumMax[0] :=সর্বাধিক 0 এবং v[0]

• 1 থেকে n – 1

  রেঞ্জের জন্য i

  • 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

  রেঞ্জে i এর জন্য

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

  • rightSumMax[i] :=rightSum[i + 1] এবং rightSum Max[i]

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

• 1 থেকে n – 2

  রেঞ্জের জন্য i

  • leftAns :=LeftAns এর সর্বাধিক, leftSum[i] + rightSumMax[i + 1]

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

• আমি n - 2 থেকে 1

  রেঞ্জে

  • rightAns :=rightAns এর সর্বোচ্চ, rightSum[i] + leftSumMax[i - 1]

• curr :=v[0], কাদানে :=v[0>

• 1 থেকে n – 1

  রেঞ্জের জন্য i

  • 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