最长上升子序列

最长上升子序列

动态规划O((n^2))

(dp[i])表示以第(i)个数结尾的最长上升子序列的长度

容易找到状态转移方程:

​ (dp[i]=max(dp[i],dp[j-1]))

for(int i = 1; i <= n; ++i) {
    for(int j = 1; j < i; ++j) {
        if(a[j] < a[i])
            dp[i] = max(dp[i], dp[j] + 1);
    }
}

贪心+二分O((nlog n))

贪心的去选择比他大的数，然后贪心的去更新(low[ans])数组中的第(i)个位置的值，使其边的更小，使能够可能有更长的上升子序列。

int a[maxn], low[maxn];
int ans=1;low[1]=a[1];
for(int i=2;i<=n;++i){
    if(a[i]<low[ans])
        low[++ans]=a[i];
    else
        low[lower_bound(low+1,low+1+ans,a[i])-low]=a[i];
}

树状数组O((nlog n))