C++-এ ম্যাক্সিমাম সার্কুলার সাবঅ্যারে সম: ক্যাডেনস অ্যালগরিদম এক্সটেনশন

একটি অ্যারে দেওয়া আছে। সার্কুলার সাবঅ্যারে (শেষ থেকে শুরুতে যেতে পারে) এর সর্বোচ্চ সম বের করুন।

উদাহরণ

ইনপুট: [2, 5, -1, 6, 9, 4, -5]

আউটপুট: 25

ব্যাখ্যা: সাবঅ্যারে [4, 2, 5, -1, 6, 9] = 25 (সার্কুলারলি)।

অ্যালগরিদম (মডিফাইড ক্যাডেনস)

1. নন-সার্কুলার ম্যাক্স সাবঅ্যারে সম = max_normal (স্ট্যান্ডার্ড ক্যাডেনস)।
2. মোট সম = total।
3. মিনিমাম সাবঅ্যারে সম = min_subarray (ক্যাডেনস মিনিমামের জন্য)।
4. সার্কুলার ম্যাক্স = total - min_subarray (যদি সব নেগেটিভ না হয়)।
5. উত্তর = max(max_normal, circular_max)।

C++ বাস্তবায়ন

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

int maximum(int arr[], int size) {
    int total = 0;
    for (int i = 0; i < size; i++) total += arr[i];
    
    int max_ending = arr[0], max_sum = arr[0];
    int min_ending = arr[0], min_sum = arr[0];
    
    for (int i = 1; i < size; i++) {
        max_ending = max(arr[i], max_ending + arr[i]);
        max_sum = max(max_sum, max_ending);
        
        min_ending = min(arr[i], min_ending + arr[i]);
        min_sum = min(min_sum, min_ending);
    }
    
    if (max_sum < 0) return max_sum; // সব নেগেটিভ
    return max(max_sum, total - min_sum);
}

int main() {
    int arr[] = {2, 5, -1, 6, 9, 4, -5};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Max Circular Sum: " << maximum(arr, size);
    return 0;
}

সময় জটিলতা

O(n) - একবার ট্রাভার্স। স্পেস O(1)।