C++-এ ডিভাইড এন্ড কংকর অ্যালগরিদম দিয়ে সর্বোচ্চ সাবঅ্যারে সম

ধরুন আমাদের একটি লিস্ট আছে ধনাত্মক এবং ঋণাত্মক মানসহ। আমাদের সান্তানিক সাবঅ্যারেটি খুঁজে বের করতে হবে যার যোগফল সর্বোচ্চ। ধরুন লিস্টটি হল {-2, -5, 6, -2, -3, 1, 5, -6}, তবে সর্বোচ্চ সাবঅ্যারে সম হল ৭। এটি হল {6, -2, -3, 1, 5}-এর যোগফল।

আমরা এই সমস্যাটি ডিভাইড এন্ড কংকর পদ্ধতিতে সমাধান করব। ধাপগুলো নিচের মতো:

ধাপসমূহ

• অ্যারেটিকে দুটি অংশে ভাগ করুন
• নিচের তিনটির সর্বোচ্চ মান বের করুন
  • বাম সাবঅ্যারের সর্বোচ্চ সাবঅ্যারে সম
  • ডান সাবঅ্যারের সর্বোচ্চ সাবঅ্যারে সম
  • মিডপয়েন্ট ক্রস করে এমন সাবঅ্যারের সর্বোচ্চ সম

C++ প্রোগ্রাম উদাহরণ

#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b)? a : b;
}

int max(int a, int b, int c) {
    return max(max(a, b), c);
}

int getMaxCrossingSum(int arr[], int l, int m, int h) {
    int sum = 0;
    int left = INT_MIN;
    for (int i = m; i >= l; i--) {
        sum = sum + arr[i];
        if (sum > left)
            left = sum;
    }
    sum = 0;
    int right = INT_MIN;
    for (int i = m+1; i <= h; i++) {
        sum = sum + arr[i];
        if (sum > right)
            right = sum;
    }
    return left + right;
}

int maxSubArraySum(int arr[], int low, int high) {
    if (low == high)
        return arr[low];
    int mid = (low + high)/2;
    return max(maxSubArraySum(arr, low, mid), maxSubArraySum(arr, mid+1, high), getMaxCrossingSum(arr, low, mid, high));
}

int main() {
    int arr[] = {-2, -5, 6, -2, -3, 1, 5, -6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, 0, n-1);
    printf("Maximum contiguous sum is %d", max_sum);
    return 0;
}

আউটপুট

Maximum contiguous sum is 7