最长上升子序列

问题抽象成最长上升子序列的思想显而易见 写法复杂度也比较高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）优化 感觉在搞笑