LIS(最长上升子序列)的一种DP思路

dp[i]表示长度为i+1的上升子序列的末尾元素的值,迭代后为==>最小值

#include <stdio.h>
#include <algorithm>
using namespace std;

const int MAX = 100000000;
void solve();

const int n = 5;
int a[5] = {4, 2, 3, 1, 5};
int dp[5];

int main()
{
    solve();
    return 0;
}

void solve()
{
    int i;
    
    fill(dp, dp + n, MAX);
    for (i = 0; i < n; i++)
    {
        *lower_bound(dp, dp + n, a[i]) = a[i];
    }
    printf("%d\n", lower_bound(dp, dp + n, MAX) - dp);
}
添加新评论