Longest non descent subsequence (LIS) (dynamic programming)

   

• State Design ：dp[i] Said to str[i] The length of the longest subsequence at the end does not decrease
•     State transition equation ：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）;
•     Of course , Later, we can also output the content of the longest non descending subsequence , Just enumerate from the back dp Decrement the value of , as long as dp The value of is equal to temp( The length of the longest subsequence decreases ) equal ,  Just put str[i] Value added to lis in , until temp==0 until .
•     Output the content of the first longest non descending subsequence ： Just start enumerating from the front .

/**
    2) State Design ：dp[i] Said to str[i] The length of the longest subsequence at the end does not decrease 
     State transition equation ：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）;
     Of course , Later, we can also output the content of the longest non descending subsequence , Just from the back 
     Start enumeration dp Decrement the value of , as long as dp The value of is equal to temp( The length of the longest subsequence decreases ) equal ,
     Just put str[i] Value added to lis in , until temp==0 until .
     Output the content of the first longest non descending subsequence ： Just start enumerating from the front .
*/

/**
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cout << "input a string:\n";
    cin >> str;
    int len=str.size();
    int dp[len],ans=0;  //dp[i] Said to str[i] The length of the longest subsequence at the end does not decrease 
    dp[0]=1;            // State transition equation ：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）

    for(int i=1;i<len;++i)
    {
        dp[i]=1;
        for(int j=0;j<i;++j)
        {
            if(str[j]<=str[i]&&dp[j]+1>dp[i])
                dp[i]=dp[j]+1;
        }
        ans=max(ans,dp[i]);
    }
    string lis; //lis Output the longest non descending subsequence 
    int temp=ans;
    for(int i=len-1;i>=0;--i)
    {
        if(dp[i]==temp)
        {
            lis=str[i]+lis;   temp Look for the result from the back , When the longest sequence does not fall 
            --temp;            When there is more than one result , The resulting sequence is the last group 
        }
    }
    cout << ans << endl;
    for(auto a:str)
        cout << a << ' ';
    cout <<  endl;
    for(auto a:dp)
        cout << a << ' ';
    cout << endl;
    cout << lis << endl;
    string first;
    temp=1;
    for(int i=0;i<len;++i)
    {
        if(dp[i]==temp)
        {
            first+=str[i];
            ++temp;
        }
    }

    cout << "first substr:\n";
    cout << first << endl;
    return 0;
}
*/

3) In order not to lower the content of the subsequence for subsequent output , You can also open one result Array ,result[i]
    Express str[i] The predecessor node of , The first node of a sequence is set to -1, Distinguish from other nodes ,
    In fact, it is used with the first program dp The output content is the same .

/**
    3) In order not to lower the content of the subsequence for subsequent output , You can also open one result Array ,result[i]
     Express str[i] The predecessor node of , The first node of a sequence is set to -1, Distinguish from other nodes ,
     In fact, it is used with the first program dp The output content is the same 
*/

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cout << "input a string:\n";
    cin >> str;
    int len=str.size();
    int dp[len];        //dp[i] Said to str[i] The length of the longest subsequence at the end does not decrease 
    dp[0]=1;            // State transition equation ：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）
    int result[len];    //result[i] Express str[i] The predecessor node of 
    result[0]=-1;       // The first node of a sequence is set to -1, Distinguish from other nodes 
    for(int i=1;i<len;++i)
    {
        dp[i]=1;
        result[i]=-1;
        for(int j=0;j<i;++j)
        {
            if(str[j]<=str[i]&&dp[j]+1>dp[i])
            {
                dp[i]=dp[j]+1;
                result[i]=j;
            }
        }
    }
    int p=0,imax=0;
    for(int i=0;i<len;++i)
    {
        if(dp[i]>imax)
        {
            imax=dp[i];
            p=i;
        }
    }
    string lis;
    for(;p!=-1;)
    {
        lis=str[p]+lis;
        p=result[p];
    }
    cout << imax << endl;
    cout << lis << endl;
    cout << " debugging :\n";
    for(auto a:str)
        cout << a << ' ';
    cout <<  endl;
    for(auto a:dp)
        cout << a << ' ';
    cout << endl;
    for(auto a:result)
        cout << a << ' ';
    cout << endl;
    return 0;
}