इस समस्या में, हमें धनात्मक पूर्णांकों की एक सरणी और एक संख्या k दी गई है। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो दिए गए आकार (के) के दो गैर-अतिव्यापी उप-सरणी का अधिकतम योग प्राप्त करेगा।
तो, मूल रूप से हमारे पास दो प्रिंट दो गैर-अतिव्यापी (विशिष्ट) उप-सरणी हैं जिनमें अधिकतम योग है और आकार k है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट -
array = {7, 1, 6, 9, 2} , k = 2 आउटपुट -
{7, 1} , {6, 9} स्पष्टीकरण -
all subarrays of size 2.
{7, 1} : sum = 7+1 = 8
{1, 6} : sum = 1+6 = 7
{6, 9} : sum = 6+9 = 15
{9, 2} : sum = 9+2 = 11
Two non-overlapping subarrays with max sums are {7,1} and {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 }