Runtime complexity & correctedness of LIS

Question

function LIS(str1){

return LISUtil(str1, 0);

function LISUtil(str1, index){
    if(index == str1.length){
        return 0;
    }
    var min = str1[index],
        len = 1;

    for(let i=index+1; i<str1.length; i++){

        if(min < str1[i]){
            len++;
            min = str1[i];
        }
    }
    return Math.max(len, LISUtil(str1, index+1));
}

}

This is what I've come up with longest increasing subsequence (yes it looks weird, but please ignore that for now!).

I've read that LIS has a runtime Complexity of 2^n. With DP, you could make it to n^2.

As I think and try my LIS function, I'm sure that it runs in n^2. It goes through n, and each index is checked O(n) times -> n^2.

I've run some test cases, and it does return correctly. But I haven't used DP...meaning it must be either of these 2.

1. My function is wrong. It does not get LIS.
2. The run time is 2^n, and I am just failing to calculate the run time properly.

Could anyone help me straighten my thoughts? Is my function wrong, is the runtime 2^n, or is it possible to get LIS without DP?

Answer 1

It does not get the LIS. For instance,

LIS([1, 6, 2, 3, 7, 4, 5])

returns 3. Should be 4.