ধরুন আমাদের একটি ডেটা লিস্ট আছে পজিটিভ এবং 네가টিভ ভ্যালুসহ। আমাদের কন্টিগুয়াস সাবঅ্যারে খুঁজে বের করতে হবে যার যোগফল সর্বোচ্চ। ধরুন লিস্টে {-2, -5, 6, -2, -3, 1, 5, -6} আছে, তবে ম্যাক্সিমাম সাবঅ্যারে সম ৭। এটি {6, -2, -3, 1, 5}-এর যোগফল।
এই সমস্যাটি ডিভাইড অ্যান্ড কঙ্কর মেথড ব্যবহার করে সমাধান করব। ধাপগুলো নিচের মত:
ধাপসমূহ −
- অ্যারেটি দুটি পার্টে ভাগ করুন।
- নিচের তিনটির ম্যাক্সিমাম বের করুন:
- বাম সাবঅ্যারের ম্যাক্সিমাম সাবঅ্যারে সম।
- ডান সাবঅ্যারের ম্যাক্সিমাম সাবঅ্যারে সম।
- মিডপয়েন্ট ক্রস করে এমন সাবঅ্যারের ম্যাক্সিমাম সম।
উদাহরণ
#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
