C++ में अधिकतम योग वृत्ताकार उपसरणी

मान लीजिए हमारे पास पूर्णांकों का एक वृत्ताकार सरणी C है जिसे सरणी A द्वारा दर्शाया गया है। हमें C के एक गैर-खाली उपसरणी का अधिकतम संभव योग ढूंढना है। एक उपसरणी में निश्चित बफर A के प्रत्येक तत्व को अधिकतम एक बार शामिल किया जा सकता है।

उदाहरण: [1,-2,3,-2] के लिए आउटपुट 3 होगा (उपसरणी [3] का योग 3)।

केडेन एल्गोरिदम + प्रीफिक्स/सफिक्स मैक्स

वृत्ताकार उपसरणी का अधिकतम योग दो मामलों में से एक हो सकता है:

1. सामान्य (गैर-वृत्ताकार) अधिकतम उपसरणी योग (केडेन एल्गोरिदम)।
2. वृत्ताकार उपसरणी: कुल योग - न्यूनतम उपसरणी योग (यदि सभी तत्व ऋणात्मक नहीं हैं)।

सरल दृष्टिकोण: max(kadane, totalSum - minSubarray) लेकिन सभी ऋणात्मक मामले को संभालें।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& v) {
        int n = v.size();
        int total = 0, maxSum = v[0], minSum = v[0];
        int curMax = 0, curMin = 0;
        
        for (int x : v) {
            curMax = max(x, curMax + x);
            maxSum = max(maxSum, curMax);
            
            curMin = min(x, curMin + x);
            minSum = min(minSum, curMin);
            
            total += x;
        }
        
        if (maxSum < 0) return maxSum; // सभी ऋणात्मक
        return max(maxSum, total - minSum);
    }
};

int main() {
    vector<int> v = {1, -2, 3, -2};
    Solution ob;
    cout << ob.maxSubarraySumCircular(v); // 3
    return 0;
}

इनपुट

[1,-2,3,-2]

आउटपुट

3