Longest increasing subsequence

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Problem

Select some item in array, and keep them ascending.
e.g.: 0 8 2 9 3 1 7
ans ==> 0 2 3 7 len=4

Method1

Binary Indexed Tree
O(nlogn)
http://codeforces.com/blog/entry/8761
We using BIT[value] to save a LIS's length ended with value.
We need to modify the 'original Binary Indexed Tree Algorithm', to update/query maxvalue from [1...val]

int BIT[MAXN];
int update(int p, val) {//add function
    for (p; p<n; p+=p&-p)
        BIT[p] = max(BIT[p], val);
}
int sum(int p) {
    int ans=0;
    for (p; p>0; p-=p)
        ans = max(ans, BIT[p]);
    return ans;
}

Method2

DP O(nlogn)
dp[i] = itemval : Existing a subsequence with length 'i' and end up with 'itemval'
e.g.: 0 8 2 9 3 1 7

---s1 0

dp[0]= 0

---s2 08

dp[0]= 0
dp[1]= x 8  <= dp[0]+'8';

---s3 082

dp[0]= 0
dp[1]= x 2  <= dp[0]+'2';

--s4 0829

dp[0]= 0
dp[1]= x 2
dp[2]= x x 9  <= dp[1]+'9';

--s5 08293

dp[0]= 0
dp[1]= x 2
dp[2]= x x 3  <= dp[1]+'3';

--s6 082931

dp[0]= 0
dp[1]= x 1  <= dp[0]+'1';
dp[2]= x x 3

---s7 0829317

dp[0]= 0
dp[1]= x 1
dp[2]= x x 3
dp[3]= x x x 7 <=dp[2]+'7';