इस समस्या में, हमें एक सरणी arr[] और एक पूर्णांक k दिया गया है। हमारा कार्य सरणी में हर Kवें तत्व को लेकर अधिकतम योग ज्ञात करना है।
समस्या विवरण: हमें सरणी के तत्वों का अधिकतम योग खोजना है जैसे कि वे k इंडेक्स दूर हों। यानी हमें योग को अधिकतम करना है:
योग = arr[i] + arr[i+k] + arr[i + 2*k] + …. arr[i + p*k], जैसे कि (i + p*k) < n
आइए एक उदाहरण से समझते हैं:
इनपुट
arr[] = {5, 3, -1, 2, 4, -5, 6}, k = 4आउटपुट
9
व्याख्या
हर kवें तत्व के सभी योग हैं: 5 + 4 = 9, 3 - 5 = -2, -1 + 6 = 5, 2, 4, -5, 6। अधिकतम 9 है।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान दो नेस्टेड लूप का उपयोग करना है, बाहरी सरणी के प्रत्येक तत्व के लिए और आंतरिक i से हर kवें तत्व का योग खोजने के लिए। यानी योग = arr[i] + arr[i + k] + arr[i + 2*k] + … + arr[i + p*k] जैसे कि (i + p*k) < n।
और अधिकतम योग लौटाएँ।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम (सरल दृष्टिकोण):
उदाहरण
#include <iostream> using namespace std; int findMaxSumK(int arr[], int n, int K){ int maxSum = -1000; for (int i = 0; i < n; i++) { int current_Sum = 0; for (int j = i; j < n; j += K) current_Sum = current_Sum + arr[j]; maxSum = max(maxSum, current_Sum); } return maxSum; } int main(){ int arr[] = {5, 3, -1, 2, 4, -5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int K = 3; cout<<"The maximum sum taking every Kth element in the array is "<<findMaxSumK(arr, n, K); return (0); }आउटपुट
The maximum sum taking every Kth element in the array is 13
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम (कुशल दृष्टिकोण - सफ़िक्स योग):
उदाहरण
#include <iostream> using namespace std; int findMaxSumK(int arr[], int n, int K) { int maxSum = -1000; int suffSum[n] = {0}; for (int i = n - 1; i >= 0; i--) { if (i + K < n) suffSum[i] = suffSum[i + K] + arr[i]; else suffSum[i] = arr[i]; maxSum = max(maxSum, suffSum[i]); } return maxSum; } int main(){ int arr[] = {5, 3, -1, 2, 4, -5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int K = 3; cout<<"The maximum sum taking every Kth element in the array is "<<findMaxSumK(arr, n, K); return (0); }आउटपुट
The maximum sum taking every Kth element in the array is 13
