इस समस्या में, हमें एक सरणी और एक संख्या k दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो दी गई सरणी को k बार दोहराकर बनी सरणी में अधिकतम सबएरे सम ढूंढेगा।
समस्या विवरण - यहां, हम दी गई सरणी को k बार दोहराकर बनी सरणी से बने सबएरे का अधिकतम सम ज्ञात करेंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - सरणी = {3, 5, 1} k = 2
आउटपुट - 18
व्याख्या -
k बार दोहराकर बनी सरणी = {3, 5, 1, 3, 5, 1} अधिकतम सबएरे सम = 3+5+1+3+5+1 = 18इस समस्या को हल करने के लिए, हम सरणी के सभी तत्वों का योग निकालेंगे।
फिर योग के आधार पर, हम सबएरे सम की गणना करेंगे।
यदि योग > 0, तो हम सरणी के योग को k बार गुणा करेंगे जो वास्तविक योग देता है।
यदि योग < 0, तो हम दो सरणी पुनरावृत्तियों को लेकर अधिकतम सम वाला सबएरे ढूंढेंगे।
उदाहरण
हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम,
#include<iostream> using namespace std; void repeatArray(int *arr, int *b, int k,int len) { int j = 0; while (k > 0){ for (int i = 0; i < len; i++) b[j++] = arr[i]; k--; } } long subArraySum(int *a,int len) { int max = 0; long newmax = 0; for (int i = 0; i < len; i++) { newmax = newmax + a[i]; if (max < newmax) max = newmax; if (newmax < 0) newmax = 0; } return max; } long findMaxSubArraySum(int *arr, int k,int len) { int arraySum = 0; long maxSum = 0; int b[(2 * len)]= {0}; repeatArray(arr, b, 2,len); for (int i = 0; i < len; i++) arraySum += arr[i]; maxSum = subArraySum(b,2*len); if (arraySum > 0) maxSum = subArraySum(b,2*len) + (k - 2) * arraySum; return maxSum; } int main() { int arr[] = { 3, 5, 1}; int length=sizeof(arr)/sizeof(arr[0]); int k = 3; cout<<"The maximum subarray sum in array formed by repeating the given array "<<k<<" times is "<<findMaxSubArraySum(arr, k,length); return 0; }आउटपुट
The maximum subarray sum in array formed by repeating the given array 3 times is 27
