इस समस्या में, हमें धनात्मक इंटीजर्स का एक ऐरे और एक संख्या k दी गई है। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो दिए गए आकार(k) के दो नॉन-ओवरलैपिंग सबऐरे का अधिकतम योग ढूंढे।
तो, मूल रूप से हमें दो नॉन-ओवरलैपिंग (अलग) सबऐरे प्रिंट करने हैं जिनका अधिकतम योग है और आकार k है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट −
array = {7, 1, 6, 9, 2} , k = 2आउटपुट −
{7, 1} , {6, 9}व्याख्या −
आकार 2 के सभी सबऐरे। {7, 1} : योग = 7+1 = 8 {1, 6} : योग = 1+6 = 7 {6, 9} : योग = 6+9 = 15 {9, 2} : योग = 9+2 = 11 अधिकतम योग वाले दो नॉन-ओवरलैपिंग सबऐरे {7,1} और {6,9} हैंइस समस्या को हल करने के लिए, एक सरल समाधान सभी सबऐरे और उनके योग ढूंढना और फिर दो अधिकतम सबऐरे की जांच करना होगा जो एक दूसरे को ओवरलैप नहीं करते हैं।
समस्या को हल करने का एक प्रभावी दृष्टिकोण प्रीफिक्स सम ऐरे का उपयोग करना होगा जो ऐरे के एलिमेंट तक सभी एलिमेंट्स का योग संग्रहीत करता है। और k एलिमेंट्स के लिए सबऐरे की जांच करके अधिकतम योग वाले सबऐरे को ढूंढना होगा।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम,
#include <bits/stdc++.h> using namespace std; int findSubArraySum(int sum[], int i, int j){ if (i == 0) return sum[j]; else return (sum[j] - sum[i - 1]); } void maxSubarray(int arr[],int N, int K){ int prefixsum[N]; prefixsum[0] = arr[0]; for (int i = 1; i < N; i++) prefixsum[i] = prefixsum[i - 1] + arr[i]; pair<int, int> resIndex = make_pair(N - 2 * K, N - K); int maxSubarraySum = findSubArraySum(prefixsum, N - 2 * K, N - K - 1) + findSubArraySum(prefixsum, N - K, N - 1); pair<int, int> secondSubarrayMax = make_pair(N - K, findSubArraySum(prefixsum, N - K, N - 1)); for (int i = N - 2 * K - 1; i >= 0; i--){ int cur = findSubArraySum(prefixsum, i + K, i + 2 * K - 1); if (cur >= secondSubarrayMax.second) secondSubarrayMax = make_pair(i + K, cur); cur = findSubArraySum(prefixsum, i, i + K - 1) + secondSubarrayMax.second; if (cur >= maxSubarraySum){ maxSubarraySum = cur; resIndex = make_pair(i, secondSubarrayMax.first); } } cout<<"{ "; for (int i = resIndex.first; i <resIndex.first + K; i++) cout<<arr[i]<<" "; cout<<"}"<<endl<<"{ "; for (int i = resIndex.second; i < resIndex.second + K; i++) cout<<arr[i]<<" "; cout<<"}"<<endl; } int main(){ int arr[] = {2, 5, 1, 2, 7, 3, 0}; int N = sizeof(arr) / sizeof(int); int K = 2; cout<<"Two non-overlapping subarrays with maximum sum are \n"; maxSubarray(arr, N, K); return 0; }आउटपुट
Two non-overlapping subarrays with maximum sum are { 2 5 } { 7 3 } 