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