अधिकतम योग बढ़ता हुआ सबसीक्वेंस

अधिकतम योग बढ़ता हुआ सबसीक्वेंस पूर्णांकों की दी गई सूची का एक सबसीक्वेंस है, जिसका योग अधिकतम है और सबसीक्वेंस में सभी तत्व बढ़ते क्रम में सॉर्टेड हैं।

मान लें एक ऐरे है जो अधिकतम योग बढ़ते सबसीक्वेंस को स्टोर करता है, जैसे कि L[i] array[i] पर समाप्त होने वाला अधिकतम योग बढ़ता हुआ सबसीक्वेंस है।

इनपुट और आउटपुट

इनपुट: पूर्णांकों का अनुक्रम
{3, 2, 6, 4, 5, 1}

आउटपुट: अधिकतम योग वाला बढ़ता हुआ सबसीक्वेंस
{3, 4, 5}

एल्गोरिदम

maxSumSubSeq(array, n)

इनपुट: संख्याओं का अनुक्रम, तत्वों की संख्या
आउटपुट: बढ़ते सबसीक्वेंस का अधिकतम योग

शुरुआत
    subSeqLen नामक ऐरे के ऐरे को आकार n का परिभाषित करें
    arr[0] को subSeqLen में जोड़ें
    i के लिए रेंज (1 से n-1) में, करें
        j के लिए रेंज (0 से i-1) में, करें
            यदि arr[i] > arr[j] और subSeqLen[i] का योग < subSeqLen[j] का योग, तो
                subSeqLen[i] := subSeqLen[j]
        पूर्ण
    पूर्ण
    arr[i] को subSeqLen[i] में जोड़ें
    res := subSeqLen[0]
    subSeqLen के सभी मानों के लिए, करें
        यदि subSeqLen[i] का योग > subSeqLen[res] का योग, तो
            res := subSeqLen[i]
    पूर्ण
    res के मान प्रिंट करें
अंत

उदाहरण (C++ कोड)

#include <iostream>
#include <vector>
using namespace std;

int findAllSum(vector arr) {
    int sum = 0;
    for(int i = 0; i < arr.size(); i++)
        sum += arr[i];
    return sum;
}

void maxSumSubSeq(int arr[], int n) {
    vector> subSeqLen(n);
    subSeqLen[0].push_back(arr[0]);
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if ((arr[i] > arr[j]) && (findAllSum(subSeqLen[i]) < findAllSum(subSeqLen[j])))
                subSeqLen[i] = subSeqLen[j];
        }
        subSeqLen[i].push_back(arr[i]);
    }
    
    vector res = subSeqLen[0];
    for(int i = 0; i < subSeqLen.size(); i++) {
        if (findAllSum(subSeqLen[i]) > findAllSum(res))
            res = subSeqLen[i];
    }
    
    for(int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = { 3, 2, 6, 4, 5, 1 };
    int n = 6;
    cout << "The Maximum Sum Subsequence is: ";
    maxSumSubSeq(arr, n);
}

आउटपुट

The Maximum Sum Subsequence is: 3 4 5