登录/注册
223. 最长上升子序列问题(挑战程序设计竞赛)
时间限制: C/C++ 1000 ms | 其他语言 2000 ms
内存限制: C/C++ 64 MB | 其他语言 128 MB
尝试次数: 242 | 通过次数: 142
尝试人数: 59 | 通过人数: 58
标签: 动态规划
难度: 中等
3
1

有一个长为 nn 的序列 a0,a1,...,an1a_0, a_1,...,a_{n - 1}

求出这个序列的最长上升子序列的长度。

上升子序列指的是对于任意的 i<ji < j 都满足 ai<aja_i < a_j 的子序列。

输入

  • 第一行为一个整数 nn
  • 第二行有 nn 个整数表示序列 aa
  • 1n10001 \leq n \leq 1000
  • 1ai1061 \leq a_i \leq 10^6

输出

  • 一个整数,表示最长上升子序列的长度
样例 1
输入
5
4 2 3 1 5
输出
3