最长上升子序列
Redraiment的走法
http://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa
问题抽象成最长上升子序列的思想显而易见 写法复杂度也比较高O(n^2) 但是过了
dp[i] 以i结尾的走法的最多步数
base case: dp[0]=2
dp[n] = 之前比a[n]小的桩的节点中 1+max dp[i]
'''
N = int(input())
a = list(map(int, input().split()))
dp = [1]*N
for i in range(N):
for j in range(i):
if a[i]>a[j]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
看到有人说可以使用 动态规划 + 贪心+ 二分 降到O（nlogn）优化 感觉在搞笑
老板电器二面152人在聊