Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में कम से कम k दूरी वाले तत्वों का अधिकतम योग उपअनुक्रम


एक पूर्णांक सरणी और मान K दिया गया है। ऐसा उपअनुक्रम ढूंढें जिसका योग अधिकतम हो और जिसमें किन्हीं दो तत्वों के इंडेक्स में कम से कम K का अंतर हो।

उदाहरण: सरणी {50, 70, 40, 50, 90, 70, 60, 40, 70, 50}, K=2 → अधिकतम योग 230।

समाधान दृष्टिकोण (DP)

MS[i] = इंडेक्स i से शुरू होने वाले वैध उपअनुक्रम का अधिकतम योग।

  • MS[N-1] = arr[N-1]।
  • i = N-2 से 0 तक पीछे जाएं:
    • यदि i + k + 1 >= N: MS[i] = max(arr[i], MS[i+1])।
    • अन्यथा: MS[i] = max(arr[i] + MS[i+k+1], MS[i+1])।
  • MS[0] वापस करें।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

int maxSum(int arr[], int N, int k) {
    int MS[N];
    MS[N - 1] = arr[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        if (i + k + 1 >= N)
            MS[i] = max(arr[i], MS[i + 1]);
        else
            MS[i] = max(arr[i] + MS[i + k + 1], MS[i + 1]);
    }
    return MS[0];
}

int main() {
    int N = 10, k = 2;
    int arr[] = {50, 70, 40, 50, 90, 70, 60, 40, 70, 50};
    cout << maxSum(arr, N, k);
    return 0;
}

आउटपुट

230
  1. - C++ में अधिकतम उपसरणी योग मॉड्यूलो m (Maximum subarray sum modulo m)

    इस समस्या में, हमें आकार n की एक सरणी और एक पूर्णांक m दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में अधिकतम उपसरणी योग मॉड्यूलो m ढूंढे। प्रोग्राम विवरण - यहां, हम उपसरणी के सभी तत्वों के योग को m से विभाजित करके प्राप्त अधिकतम मान ढूंढेंगे। आइए एक उदाहरण से समझते हैं: इनपुट - सरणी = {4

  1. - C++ में दिए गए योग के साथ अधिकतम आकार का सबसेट

    समस्या कथनN तत्वों का एक एरे और योग दिया गया है। हमें उस अधिकतम आकार के सबसेट का आकार ढूंढना है जिसका योग दिए गए योग के बराबर हो।उदाहरणयदि इनपुट एरे arr = { 2, 3, 5, 10 } है और योग = 20 है तो आउटपुट 4 होगा क्योंकि −2 + 3 + 5 + 10 = 20 जो दिए गए योग के बराबर है।एल्गोरिदमहम इस समस्या को हल करने

  1. - C++ का उपयोग करके मैट्रिक्स में अधिकतम योग वाला कॉलम खोजें

    मान लीजिए हमारे पास M x N आकार का एक मैट्रिक्स है। हमें वह कॉलम ढूंढना है जिसका योग अधिकतम है। इस प्रोग्राम में हम किसी ट्रिकी दृष्टिकोण का पालन नहीं करेंगे, बल्कि सरणी को कॉलम-वार पार करेंगे, प्रत्येक कॉलम का योग प्राप्त करेंगे, और यदि योग अधिकतम है, तो उस योग और कॉलम इंडेक्स को प्रिंट करेंगे। उदा