इस समस्या में, हमें आकार n की एक सरणी arr[] और एक पूर्णांक k दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो बार-बार संयोजन के बाद बनी सरणी में अधिकतम उपसरणी योग ढूंढे।
समस्या विवरण
हम उस उपसरणी का अधिकतम योग ढूंढेंगे जो उस सरणी से लिया गया है जो arr को k बार दोहराने के बाद बनती है।
उदाहरण
इनपुट
arr[] = {-9, -5, 14, 6} k = 2
आउटपुट
26
व्याख्या
दोहराने के बाद नई सरणी: {-9, -5, 14, 6, -9, -5, 14, 6}
अधिकतम योग वाली उपसरणी = {14, 6, -9, -5, 14, 6}
योग = 26
समाधान दृष्टिकोण
एक सरल समाधान एक नई सरणी बनाना है जो arr[] को k बार संयोजित करके बनेगी, और फिर अधिकतम योग वाली उपसरणी ढूंढना। इसके लिए, सबसे अच्छी विधि कडाने के एल्गोरिदम (Kadane's Algorithm) का उपयोग करना होगा।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#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
यह दृष्टिकोण अच्छा है लेकिन मॉड्यूलर अंकगणित का उपयोग करके समस्या को हल करने का एक अधिक कुशल दृष्टिकोण संभव है।
मॉड्यूलर अंकगणित (Modular Arithmetic) वह है जब हम समीकरण का शेष प्राप्त करने के लिए मॉड्यूलो ऑपरेटर का उपयोग करते हैं।
समस्या को हल करने के लिए, हम बार-बार संयोजन करके सरणी बनाने के बजाय मॉड्यूलर अंकगणित का उपयोग करेंगे। बाकी समाधान वही रहता है।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#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
