मान लीजिए हमारे पास धनात्मक और ऋणात्मक मानों वाले डेटा की एक सूची है। हमें सन्निहित सबएरे का योग ढूंढना है जिसका योग सबसे बड़ा है। मान लीजिए सूची में {-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("अधिकतम सन्निहित योग %d है", max_sum); } आउटपुट
अधिकतम सन्निहित योग 7 है
