关于最长上升子序列的相关讨论

最近，在题目中，遇见了最长不上升子序列的求解，所以，我特地思考了关于上升子序列的4中相关情况的求解。

最长严格上升子序列

int LIS(int n)
{
    int len = 1;
    dp[1] = a[1];
    
    for(int i=2; i<=n; ++i)
    {
        if(a[i] > dp[len])
        {
            
            dp[++len] = a[i];
        }
        else
        {
            int pos = lower_bound(dp, dp+len, a[i]) - dp;
            dp[pos] = a[i];
        }
    }
    return len;
}

最长不严格上升子序列

int LIS(int n)
{
    int len = 1;
    dp[1] = a[1];
    
    for(int i=2; i<=n; ++i)
    {
        if(a[i] > =dp[len])
        {
            
            dp[++len] = a[i];
        }
        else
        {
            int pos = upper_bound(dp, dp+len, a[i]) - dp;
            dp[pos] = a[i];
        }
    }
    return len;
}

最长严格下降子序列

int LIS(int n)
{
    int len = 1;
    dp[1] = a[1];
    
    for(int i=2; i<=n; ++i)
    {
        if(a[i] < dp[len])
        {
            
            dp[++len] = a[i];
        }
        else
        {
            int pos = lower_bound(dp, dp+len, a[i], greater<int>()) - dp;
            dp[pos] = a[i];
        }
    }
    return len;
}

最长不严格下降子序列

int LIS(int n)
{
    int len = 1;
    dp[1] = a[1];
    
    for(int i=2; i<=n; ++i)
    {
        if(a[i] <= dp[len])
        {
            
            dp[++len] = a[i];
        }
        else
        {
            int pos = upper_bound(dp, dp+len, a[i], greater<int>()) - dp;
            dp[pos] = a[i];
        }
    }
    return len;
}