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

C++ में विशिष्ट अंतर वाले जोड़ों का अधिकतम योग


सरणी और मान K दिया गया है। ऐसे जोड़े बनाएं जिनका अंतर K से कम हो, और असंयुक्त जोड़ों के तत्वों का अधिकतम योग खोजें।

उदाहरण: {3, 5, 10, 15, 17, 12, 9}, K=4 → अधिकतम योग 62।

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

  1. सरणी को सॉर्ट करें।
  2. dp[i] = पहले i+1 तत्वों से अधिकतम योग।
  3. dp[0] = 0।
  4. i = 1 से N-1 तक:
    • dp[i] = dp[i-1] (i-वां तत्व न लें)।
    • यदि arr[i] - arr[i-1] < K:
      • यदि i >= 2: dp[i] = max(dp[i], dp[i-2] + arr[i] + arr[i-1])।
      • अन्यथा: dp[i] = max(dp[i], arr[i] + arr[i-1])।
  5. dp[N-1] वापस करें।

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

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

int maxSumPairWithDifferenceLessThanK(int arr[], int N, int K) {
    sort(arr, arr + N);
    int dp[N];
    dp[0] = 0;
    for (int i = 1; i < N; i++) {
        dp[i] = dp[i - 1];
        if (arr[i] - arr[i - 1] < K) {
            if (i >= 2) dp[i] = max(dp[i], dp[i - 2] + arr[i] + arr[i - 1]);
            else dp[i] = max(dp[i], arr[i] + arr[i - 1]);
        }
    }
    return dp[N - 1];
}

int main() {
    int arr[] = {3, 5, 10, 15, 17, 12, 9};
    int N = sizeof(arr) / sizeof(int);
    int K = 4;
    cout << maxSumPairWithDifferenceLessThanK(arr, N, K);
    return 0;
}

आउटपुट

62
  1. - C++ में ऐरे में अधिकतम संतुलन योग

    समस्या कथन एक ऐरे arr[] दिया गया है। इंडेक्स i के लिए arr[] में अधिकतम प्रीफिक्स योग का मान ढूंढें जो सफिक्स योग भी हो। उदाहरण यदि इनपुट ऐरे है - Arr[] = {1, 2, 3, 5, 3, 2, 1} तो आउटपुट 11 है - प्रीफिक्स योग = arr[0..3] = 1 + 2 + 3 + 5 = 11 और सफिक्स योग = arr[3..6] = 5 + 3 + 2 + 1 = 11 एल्गोरिदम

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

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

  1. - C++ में पेयर्स की अधिकतम लंबाई चेन

    पेयर्स की एक चेन दी गई है। प्रत्येक पेयर में दो इंटीजर हैं और पहला इंटीजर हमेशा छोटा होता है, और दूसरा बड़ा, यही नियम चेन निर्माण के लिए भी लागू होता है। एक पेयर (x, y) को पेयर (p, q) के बाद तभी जोड़ा जा सकता है जब q < x हो।इस समस्या को हल करने के लिए, सबसे पहले हमें दिए गए पेयर्स को पहले एलिमेंट