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);
}