Longest Increasing Subsequence

LIS.md

##Longest Increasing Subsequence

之前的一篇GIST其实已经解决了这个问题，只不过现在使用STL技术更加优雅地写出来了

这个问题可以用DP解决，如果定义

dp[i] = 以ai为结尾的最长上升子序列的长度

那么转移方程

dp[i] = max{1,dp[j]+1 | j < i and aj < ai}

那么可以很轻松的写出O(n^2)的算法

    int n;
    int a[N];
    
    int dp[N];
    int solve(){
        int result = 0;
        for(auto i = 0; i < n; i++){
            dp[i] = 1;
            for(auto j = 0; j < i; j++){
                dp[i] = max(dp[i],dp[j]+1);
            }
            result = max(result,dp[i]);
        }
        return result;
    }

然后，如果定义 dp[i] = 长度为i+1的上升子序列末尾元素的最小值

那么转移方程就为 dp[i] = min(dp[i],aj)

使用二分查找可以构造复杂度为O(nlogn)的算法

    int dp[N];
    int solve(){
        fill(dp,dp+n,INT_MAX);
        for(auto i = 0; i < n; i++){
            *lower_bound(dp,dp+n,a[i]) = a[i];
        }
        return lower_bound(dp,dp+n,INT_MAX)-dp;
    }