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

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

আমরা Divide and Conquer পদ্ধতি ব্যবহার করে এই সমস্যার সমাধান করব। ধাপগুলো নিচের মত দেখাবে −

পদক্ষেপ −

• অ্যারেটিকে দুটি ভাগে ভাগ করুন
• নিম্নলিখিত তিনটির মধ্যে সর্বাধিক খুঁজুন
  • বাম সাবয়ারের সর্বোচ্চ সাবয়ারের যোগফল
  • সর্বোচ্চ সাবয়ারের সমষ্টি ডান সাবয়ারের
  • সর্বোচ্চ সাবয়ারের যোগফল যেমন সাব্যারে মধ্যবিন্দু অতিক্রম করে

উদাহরণ

#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);
}

আউটপুট

Valid String