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.