সার্কুলার সাবঅ্যারে সর্বোচ্চ সমষ্টি C++-এ

ধরা যাক একটি সার্কুলার অ্যারে C আছে যা A দ্বারা রিপ্রেজেন্ট করা হয়েছে, আমরা C-এর একটি নন-এম্পটি সাবঅ্যারের সর্বোচ্চ সম্ভাব্য সমষ্টি বের করতে চাই। এছাড়া একটি সাবঅ্যারে ফিক্সড বাফার A-এর প্রতিটি উপাদানকে সর্বোচ্চ একবার অন্তর্ভুক্ত করতে পারে। যদি অ্যারে হয় [1,-2,3,-2], তবে আউটপুট হবে 3। কারণ সাবঅ্যারে [3] সর্বোচ্চ সমষ্টি 3 দেয়।

সমাধানের ধাপগুলো −

• n := v-এর আকার

• leftSum, leftSumMax, rightSum, rightSumMax নামক চারটি অ্যারে তৈরি করব সবই আকার n

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

• i = 1 থেকে n-1 পর্যন্ত

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

  • leftSumMax[i] := leftSum[i] এবং leftSumMax[i-1]-এর ম্যাক্সিমাম

• rightSum[n-1] := v[n-1], rightSumMax[n-1] := 0 এবং v[n-1]-এর ম্যাক্সিমাম

• i = n-2 থেকে 0 পর্যন্ত

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

  • rightSumMax[i] := rightSum[i+1] এবং rightSumMax[i]-এর ম্যাক্সিমাম

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

• i = 1 থেকে n-2 পর্যন্ত

  • leftAns := leftAns এবং leftSum[i] + rightSumMax[i+1]-এর ম্যাক্সিমাম

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

• i = n-2 থেকে 1 পর্যন্ত

  • rightAns := rightAns এবং rightSum[i] + leftSumMax[i-1]-এর ম্যাক্সিমাম

• curr := v[0], kadane := v[0]

• i = 1 থেকে n-1 পর্যন্ত

  • curr := v[i] এবং 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