इस समस्या में, हमें n आकार का एक सरणी arr[] और एक पूर्णांक k दिया जाता है। हमारा कार्य दोहराए गए संयोजन के बाद बनाए गए सरणी में अधिकतम सबएरे योग खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण - हम पाएंगे कि उप-सरणी का अधिकतम योग उस सरणी से लिया गया है जो एआर, k बार दोहराने के बाद बनाई गई है।
उदाहरण
समस्या को समझने के लिए एक उदाहरण लेते हैं।
इनपुट
arr[] = {−9, −5, 14, 6} k = 2 आउटपुट
26
स्पष्टीकरण
New array after repeating : {−9, −5, 14, 6, −9, −5, 14, 6}
Subarray with maximum sum = {14, 6, −9, −5, 14, 6}
Sum = 26 समाधान दृष्टिकोण
एक सरल उपाय यह है कि एक नई सरणी बनाई जाए जो एआर [], के समय को संयोजित करने के बाद बनाई जाएगी, और फिर अधिकतम योग के साथ उपसरणी खोजें। इसके लिए, सबसे अच्छा तरीका कडाने के एल्गोरिथ्म का उपयोग करना होगा।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
int newArr[2*n];
for(int i = 0; i < k*n; i++)
newArr[i] = arr[i%n];
int maxSum = −1000, sum = 0;
for (int i = 0; i < k*n; i++) {
sum = sum + newArr[i];
if (maxSum < sum)
maxSum = sum;
if (sum < 0)
sum = 0;
}
return maxSum;
}
int main(){
int arr[] = { −9, −5, 14, 6 };
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum subarray sum in an array created after repeated concatenation is "<<calcMaxSubArraySum(arr, n, k);
return 0;
} आउटपुट
The maximum subarray sum in an array created after repeated concatenation is 26
यह दृष्टिकोण अच्छा है लेकिन मॉड्यूलर अंकगणित का उपयोग करके समस्या को हल करने के लिए एक अधिक कुशल दृष्टिकोण संभव है।
मॉड्यूलर अंकगणित तब होता है जब हम शेष समीकरण प्राप्त करने के लिए मॉड्यूल ऑपरेटर का उपयोग करते हैं।
समस्या को हल करने के लिए, हम बार-बार संयोजन द्वारा सरणी बनाने के बजाय मॉड्यूलर अंकगणित का उपयोग करेंगे। बाकी समाधान वही रहता है।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
int maxSum = −1000, sum = 0;
for (int i = 0; i < k*n; i++) {
sum = sum + arr[i%n];
if (maxSum < sum)
maxSum = sum;
if (sum < 0)
sum = 0;
}
return maxSum;
}
int main(){
int arr[] = { −9, −5, 14, 6 };
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum subarray sum in an array created after
repeated concatenation is "<<calcMaxSubArraySum(arr, n, k);
return 0;
} आउटपुट
The maximum subarray sum in an array created after repeated concatenation is 26