अधिकतम योग M तत्व चुनें जैसे कि सन्निहित दोहराव C++ में K से अधिक न हो

इस समस्या में, हमें array arr[] और दो पूर्णांक M और K दिए जाते हैं। हमारा कार्य दिए गए सरणी के तत्वों का उपयोग करके एक Array बनाना है। नई सरणी का आकार M होना चाहिए और K से बड़े आकार के किसी भी उप-सरणी में सभी तत्व समान नहीं हो सकते। हमें बनाई गई सरणी द्वारा अधिकतम संभव राशि प्रिंट करनी होगी।

आइए समस्या को समझने के लिए एक उदाहरण लेते हैं

इनपुट - एआर [] ={1, 2, 4, 5, 7}, एम =5, के =2

स्पष्टीकरण - सरणी बनाई गई है जो {7, 7, 5, 7, 7} की स्थिति को संतुष्ट करती है। यहां, 2 से अधिक आकार वाले किसी भी उप-सरणी में सभी तत्व समान नहीं हो सकते हैं।

इस समस्या को हल करने के लिए, हमें अधिकतम मान वाले तत्व का उपयोग करके एक सरणी बनाने की आवश्यकता है। लेकिन हम k समय से अधिक अधिकतम तत्व का उपयोग नहीं कर सकते हैं, इसलिए k समय के बाद, हमें सरणी के दूसरे अधिकतम तत्व का उपयोग करना होगा। सरणी में प्रत्येक k अधिकतम मान के बाद एक सेकंड का अधिकतम मान डालें और M लंबाई की एक सरणी बनाएं। अंतिम आउटपुट इस सरणी के सभी तत्वों का योग होगा।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,

#include <iostream>
using namespace std;
long int arraySum(int arr[], int n, int m, int k){
   int max1 = arr[0], max2 = arr[0];
   for (int i = 1; i < n; i++) {
      if (arr[i] > max1) {
         max2 = max1;
         max1 = arr[i];
      }
      else if (arr[i] > max2)
         max2 = arr[i];
   }
   int max2count = m / (k + 1);
   long int sum = max2count * max2 + (m - max2count) * max1;
   return sum;
}
int main() {
   int arr[] = { 1, 3, 6, 7, 4, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int m = 9, k = 2;
   cout<<"The maximum sum of array created from the given array such that no subarray of size greater    than "<<k<<" will have same elements is ";
   cout<<arraySum(arr, n, m, k);
   return 0;
}

आउटपुट

The maximum sum of array created from the given array such that no subarray of size greater than 2 will have same elements is 60