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)