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)