The following code traverses the list once and finds the LIS. I don't see why the DP algorithm should take O(n2).

```
//C
int lis(int *a, int l){
if(l == 0) return 1;
else if(a[l] > a[l - 1]) return 1 + lis(a, l - 1);
else return lis(a, l - 1);
}
int main(){
int a[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
cout << lis(a, sizeof(a)/sizeof(a[0]) - 1);
}
% erlang
lis([_H]) -> 1;
lis([H1, H2 |T]) when H1 > H2 -> 1 + lis([H2|T]);
lis([_H|T]) -> lis(T).
main() -> lis(lists:reverse([ 10, 22, 9, 33, 21, 50, 41, 60 ])).
```

# Best How To :

Your current implementation of `lis/1`

function is O(n), I don't see any reasons to doubt. But there is some problem. You implementation doesn't actually calculate valid LIS. Try

`lis(lists:reverse([1,2,3,4,1,2]))`

for error example. Longest increasing sequense is [1,2,3,4], right? But your algorith returns 6 as result.

First error in your algorithm in that you increase `result`

each time, when you encountered element that greater than previous. But you should increase `result`

only if current element is greater that *greatest element* of your current LIS. So (according example above) you should remember `4`

and not increase `result`

after you detected then `2`

is greater than `1`

.

But this not only thing you have to do. Consider sequence `1 2 3 6 4 5`

. For 5 first elements LIS has length of 4. But there is TWO possible options there - either `1 2 3 4`

or `1 2 3 6`

. Which you should take as actual LIS?

And so on, and so on...

Another example comes directly from wiki page.

Sequence `[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]`

has LIS `[0, 2, 6, 9, 13, 15]`

(e.g., `6`

elements), but your algorythm says `9`

.

And, (correct me, if I'm wrong), LIS implementation must return subsequence itself, but not only its length.