Сложность исполнения и исправление 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));
}

}

Это то, к чему я придумала самую длинную увеличивающуюся подпоследовательность (да, это выглядит странно, но пока игнорируйте это!).

Я читал, что LIS имеет Сложность выполнения 2^n. С DP, вы можете сделать это до п ^2.

Поскольку я думаю и пробую свою функцию LIS, я уверен, что она работает в n^2. Он проходит через n, и каждый индекс проверяется O(n) раз -> n^2.

Я запустил несколько тестовых случаев, и он возвращается правильно. Но я не использовал DP... значит, это должен быть любой из этих 2.

1. Моя функция неверна. Это не получает LIS.
2. Время выполнения равно 2^n, и я просто не могу правильно рассчитать время выполнения.

Может ли кто-нибудь помочь мне исправить мои мысли? Моя функция неверна, среда выполнения 2 ^ n или возможно получить LIS без DP?

Answer 1

Это не получить LIS. Например,

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

возвращает 3. Должно быть 4.