最长上升/下降子序列的长度（动态规划）

一.最长上升子序列

1.什么是最长上升子序列:

定义：子序列是从数组中删除部分元素（不改变顺序）得到的序列。不下降指序列中每个元素>=前一个元素。LIS即长度最长的不下降子序列。
示例：数组nums=[3,1,2,4,3]的LIS为[1,2,4]或[1,2,3]，
长度=3。
应用价值：任务调度、股票买卖等。

2.动态规划原理:

核心思想：用动态规划记录以每个元素结尾的LIS长度。
状态定义：dp[i]表示以a[i]结尾的最长不下降子序列长度。
转移方程：dp[i] = max(dp[j]+1),其中j<i且a[j]≤a[i]。
初始条件：所有dp[i]=1（单个元素自成子序列）。
最终结果：max（dp[0...n-1])即为LIS长度。

3.数据示例:

        原数组a记录具体数据

3	1	2	4	3
0	1	2	3	4

                i=0:        nums[0]=3→无前驱元素，dp[0]=1
                i=1:        nums[1]=1→j=0(3>1不满足)→dp[1]=1
                i=2:        nums[2]=2→j=1(1<2→dp[1]+1=2)→dp[2]=2
                i=3:        nums[3]=4→j=0,1,2（取j=2,dp[2]+1=3)→dp[3]=3
                i=4:        nums[4]=3→j=0,1,2（取j=2,dp[2]+1=3）→dp[4]=3

        dp[i]记录到i位置，最长不下降子序列长度

1	1	2	3	3
0	1	2	3	4

4.程序实现：

初始化：将dp数组的所有元素初始化为1，因为每个元素自身都是一个长度为1的子序列。同时，max_len也初始化为1。
双重循环：外层循环遍历数组中的每个元素1（从1开始），内层循环遍历i之前的所有元素j，以检查是否可以构成更长的子序列。
条件判断：如果a[j]≤a[i]，说明a[i]可以接在a[j]后面形成一个更长的不下降子序列。此时，更新dp[i]为dp[j]+1和当前dp[i]中的较大值。
实时更新：在每次内层循环结束后，将max_len更新为当前max_len和dp[i中的较大值。最终，max_len就是整个数组的LIS长度。

5.代码展示：

如下

方法一：

1.最长上升或者持平子序列

#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
//最长不下降子序列（上升或者持平）
int a[110];
int dp[110];
int n;
int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    //1.初始化
    dp[1] = 1;
    for(int i = 2;i<=2;i++)
    {
        dp[i] = 1;//最少可以连续1个不下降子序列
        for(int j = 1;j<i;j++)
        {
            if(a[j]<=a[i])
            {
                dp[1] = max(dp[i],dp[j]+1);
            }
        }
    }
    cout<<dp[n];
}

2.最长上升子序列

#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
//最长不下降子序列（上升或者持平）
int a[110];
int dp[110];
int n;
int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    //1.初始化
    dp[1] = 1;
    for(int i = 2;i<=2;i++)
    {
        dp[i] = 1;//最少可以连续1个不下降子序列
        for(int j = 1;j<i;j++)
        {
            if(a[j]<=a[i])
            {
                dp[1] = max(dp[i],dp[j]+1);
            }
        }
    }
    int ma = -1;
    for(int i = 1;i<=n;i++)
    {
        ma = max(dp[1],ma);
    }
    cout<<ma;
    return 0;
}

方法二：

1.优化：

核心思想：贪心策略+二分查找，维护“最小末尾元素数组”tails。tails数组定义：tails[len]表示长度为len+1的LIS的最小末尾元素。

更新规则：遍历a[i]，在tails中二分查找第一个>a[i]的位置pos：
-若pos = len:tails.push_back(nums[i]),len++
-否则：tails[pos]=a[i]
最终LIS长度：len

2.数据示例：

原数组a记录具体数据

3	1	2	4	3
0	1	2	3	4

        示例数组：a=[3，1，2，4，3]，tails数组动态更新过程：
                a[0]=3:        tails为空→tails=[3].len=1
                a[1]=1:        二分查找pos=0→tails[0]=1，tails=[1]
                a[2]=2:        二分查找pos=1→tails.push_back(2).tails=[1,2]
                a[3]=4:        二分查找pos=2→tails.push_back（4).tails=[1,2,4]
                a[4]=3:        二分查找pos=2→tails[2]=3.tails=[1.2.3]
                最终LIS长度：len=3

        数组tail记录不同长度子序列的最小末尾元素

1	2	3
0	1	2	3	4

3.程序实现：

二分查找：使用lower_bound函数在tails数组中查找第一个大于等于当前元素x的位置pqs
添加/替换：如果pos等于tails的长度，说明x是目前最大的元素，将其添加到tails末尾；否则，将tails[pos]替换为×，以维护“最小末尾元素”的性质。
返回结果：遍历完成后，tails数组的长度即为最长不下降子序列的长度。

4.代码展示：

如下

1.最长上升子序列

#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
//最长不下降子序列（上升或者持平）
int a[110];
int dp[110];
int n;
int ldp = 0;
int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i = 1;i<=n;i++)
    {
        bool flag = true;
        for(int j = 1;j<=ldp;j++)
        {
            if(a[i]<=dp[j])
            {
                dp[j] = a[i];
                flag = false;
                break;
            }
        }
        if(flag == true) dp[++ldp] = a[i];
    }
    cout<<ldp;
    return 0;
}