# Found a solution in O(N)

#1

I came up with this solution that walks the array only once. There is a `while` inside but don’t let it deceive you, it will only run one statement per element at most during the whole program. But I can’t seem to get pass this test case and I’m not sure why. Even when done manually I’m getting the same result as the algorithm (`11`). So maybe I’m not getting the problem correctly.

``````module.exports = {
//param A : array of integers
//return an integer
lis : function(A){
let longest = [A[0]];
let aux = [A[0]];
for(let i = 1; i < A.length; i++) {

// Push the number if greater than the tip
if(A[i] > longest[longest.length-1]) {
longest.push(A[i]);
} else if(A[i] > longest[longest.length - 2]) {
longest[longest.length - 1] = A[i]; // Replace tip
}

// Push to aux if greater
if(A[i] > aux[aux.length - 1]) {
aux.push(A[i]);
} else if(A[i] > aux[aux.length - 2]) {
aux[aux.length - 1] = A[i];
} else {
// Restart aux array from higest possible position
while(aux[aux.length - 1] > A[i]) aux.pop();
aux.push(A[i]);
}

// Replace sequence when aux is longer
if(aux.length >= longest.length) {
longest = aux;
aux = [];
}

// console.log('%i: %s (%i)\n',i, longest, longest.length, newsub, '\n');
}
return longest.length;
}
};
``````

Failing at:

``````[ 69, 54, 19, 51, 16, 54, 64, 89, 72, 40, 31, 43, 1, 11, 82, 65, 75, 67, 25, 98, 31, 77, 55, 88, 85, 76, 35, 101, 44, 74, 29, 94, 72, 39, 20, 24, 23, 66, 16, 95, 5, 17, 54, 89, 93, 10, 7, 88, 68, 10, 11, 22, 25, 50, 18, 59, 79, 87, 7, 49, 26, 96, 27, 19, 67, 35, 50, 10, 6, 48, 38, 28, 66, 94, 60, 27, 76, 4, 43, 66, 14, 8, 78, 72, 21, 56, 34, 90, 89 ]
``````

(Returning `11` instead of `15`)