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

C++ में एक उपसर्ग से अधिकतम योग बढ़ता उपअनुक्रम और उपसर्ग के बाद एक दिया गया तत्व अनिवार्य है

समस्या विवरण

इस समस्या में, हमें N पूर्णांकों की एक सरणी arr[] और दो सूचकांक मान x और y दिए गए हैं। हमारा कार्य C++ में एक उपसर्ग से अधिकतम योग बढ़ते उपअनुक्रम को खोजने के लिए एक प्रोग्राम बनाना है और उपसर्ग के बाद एक दिया गया तत्व अनिवार्य है।

हम इंडेक्स x तक बढ़ते क्रम का अधिकतम योग ढूंढेंगे और इंडेक्स y पर तत्व को शामिल करेंगे।

उदाहरण

इनपुट

arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6

आउटपुट

26

व्याख्या

हम इंडेक्स 3 तक उपअनुक्रम लेंगे और अंत में arr[6] = 11 को शामिल करेंगे।

उपअनुक्रम है {1, 5, 9, 11}। योग = 1+5+9+11 = 26

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

एक सरल दृष्टिकोण x इंडेक्स तक एक नई सरणी बनाना और फिर अंत में इंडेक्स y पर तत्व जोड़ना है। फिर सभी बढ़ते उपअनुक्रमों की गणना करें और फिर उन सभी को छोड़ दें जो तत्व arr[y] को शामिल नहीं कर सकते, और maxSum ढूंढें।

समस्या को हल करने का एक और प्रभावी दृष्टिकोण डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करना है। विचार एक 2-D सरणी DP[][] बनाने का है, और बढ़ते उपअनुक्रम के अधिकतम योग को संग्रहीत करना है। DP[x][y] पर मान इंडेक्स x तक तत्व arr[y] को शामिल करके अधिकतम योग देगा।

C++ कार्यान्वयन (2-D DP)

#include <iostream>
using namespace std;

int DP[100][100];

void preCalcMaxSum(int arr[], int N){
    for (int i = 0; i < N; i++) {
        if (arr[i] > arr[0])
            DP[0][i] = arr[i] + arr[0];
        else
            DP[0][i] = arr[i];
    }
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[j] > arr[i] && j > i) {
                if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
                    DP[i][j] = DP[i - 1][i] + arr[j];
                else
                    DP[i][j] = DP[i - 1][j];
            }
            else
                DP[i][j] = DP[i - 1][j];
        }
    }
}

int main() {
    int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
    int N = sizeof(arr) / sizeof(arr[0]);
    int x = 4, y = 6;
    preCalcMaxSum(arr, N);
    cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
    cout<<DP[x][y];
    return 0;
}

आउटपुट

The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26

कुशल दृष्टिकोण (1-D DP)

इंडेक्स x तक बढ़ते उपअनुक्रम का अधिकतम योग ढूंढने का एक कुशल दृष्टिकोण इस तरह से है कि क्रम का सबसे बड़ा तत्व इंडेक्स y पर तत्व से कम हो। इसके लिए हम फिर से डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।

#include <iostream>
using namespace std;

int calcMaxSum(int arr[], int n, int x, int y){
    int DP[x] = {0};
    int maxSum = -1;
    for (int i = 0; i <= x; i++)
        DP[i] = arr[i];
    for (int i = 0; i <= x; i++) {
        if (arr[i] >= arr[y]) {
            continue;
        }
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                DP[i] += arr[j];
            maxSum = max(maxSum, DP[i]);
        }
    }
    if (maxSum == -1) {
        return arr[y];
    }
    return maxSum + arr[y];
}

int main(){
    int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
    int N = sizeof(arr) / sizeof(arr[0]);
    int x = 4, y = 6;
    cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
    cout<<calcMaxSum(arr, N, x, y);
    return 0;
}

आउटपुट

The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
  1. - C++ में दी गई रेंज से अधिकतम बिटवाइज AND पेयर

    समस्या कथन एक रेंज [L, R] दी गई है, कार्य एक पेयर (X, Y) ढूंढना है जैसे कि L ≤ X < Y ≤ R और X & Y सभी संभावित पेयर्स में अधिकतम हो, फिर मिले पेयर का बिटवाइज AND प्रिंट करें। उदाहरण यदि L = 1 और R = 10 तो अधिकतम बिटवाइज AND मान 8 है जिसे निम्नानुसार बनाया जा सकता है: 1000 # 8 का बाइनरी प्रतिनिध

  1. - C++ में अधिकतम एक तत्व हटाकर अधिकतम सबएरे योग को अधिकतम करना

    समस्या कथन N पूर्णांकों का एक ऐरे arr[] दिया गया है। कार्य पहले अधिकतम सब-एरे योग ढूंढना है और फिर सब-एरे से अधिकतम एक तत्व हटाना है। अधिकतम एक तत्व हटाएं ताकि हटाने के बाद अधिकतम योग अधिकतम हो। यदि दिया गया इनपुट ऐरे है {1, 2, 3, -2, 3} तो अधिकतम सब-एरे योग {2, 3, -2, 3} है। फिर हम -2 हटा सकते है

  1. - C++ में अधिकतम आकार 2 और दी गई वैल्यू द्वारा सीमित योग के साथ न्यूनतम पार्टीशन

    समस्या विवरण सकारात्मक संख्याओं का एक ऐरे arr[] दिया गया है, ऐरे में न्यूनतम संख्या में सेट ढूंढें जो निम्नलिखित गुण को संतुष्ट करते हैं: एक सेट में अधिकतम दो एलिमेंट्स हो सकते हैं। दोनों एलिमेंट्स का सन्निकट होना आवश्यक नहीं है। सेट के एलिमेंट्स का योग दी गई Key से कम या बराबर होना चाहिए। यह माना