【POJ 3903】Stock Exchange

【POJ 3903】Stock Exchange
폭력을 행사하는 LIS가 시간을 초과했다는 것을 알고 보니 2분의 LIS가 있었다는 것을 알게 되었다. 고루하고 견문이 좁았다...원리는 간단합니다. LIS의 dp수조는 반드시 점차적으로 증가할 것입니다. 그래서 폭력적일 때 고친 것도 >x의 첫 번째 dp점입니다.TOT가 약해졌어요.
코드는 다음과 같습니다.

#include <iostream>
#include <cstdio>

using namespace std;

int dp[100001];
int len;

int main()
{
    int n,i,j,a,l,r,mid;
    dp[0] = -1;
    while(~scanf("%d",&n))
    {
        len = 0;
        for(i = 0; i < n; ++i)
        {
            scanf("%d",&a);
            if(a > dp[len]) dp[++len] = a;
            else
            {
                l = 0,r = len;
                while(l <= r)
                {
                    mid = (l+r)>>1;
                    if(dp[mid] >= a) r = mid-1;
                    else l = mid+1;
                }
                dp[l] = a;
            }
        }
        printf("%d
",len);
    }
    return 0;
}