मान लीजिए कि हमारे पास सकारात्मक और नकारात्मक मूल्यों वाले डेटा की एक सूची है। हमें सन्निहित उप-सरणी का योग ज्ञात करना है जिसका योग सबसे बड़ा है। मान लीजिए सूची में {-2, -5, 6, -2, -3, 1, 5, -6} है, तो अधिकतम उप-सरणी का योग 7 है। यह {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
