0
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?

user2130500
  • 15
  • 1
  • 4
  • LIS can be done in O(n log(n)) complexity, see [this thread](http://stackoverflow.com/questions/3992697/longest-increasing-subsequence?s=11%7C5.0146) for good algorithms. – Gribouillis Dec 21 '16 at 15:25

1 Answers1

0

It does not get the LIS. For instance,

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

returns 3. Should be 4.

njlarsson
  • 2,128
  • 1
  • 18
  • 27
  • Sorry for the late reply, I was out of country for a while. Could you tell me which part seems to be making it wrong? I went through couple of times, but I think it makes sense and it should in fact return the correct LIS. – user2130500 Dec 27 '16 at 19:55
  • Sorry, I'm afraid I neither know why it doesn't work nor why it should work. But with this reasonably small case showing one instance where it goes wrong, you should be able to follow the execution of that (with trace printouts or a debugger) to see where it doesn't behave ther way you expect it to. – njlarsson Dec 28 '16 at 22:27