javascript - 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，您可以达到 n^2。

正如我思考和尝试我的 LIS 函数一样，我确信它可以在 n^2 中运行。它经过 n，每个索引检查 O(n) 次 -> n^2。

我已经运行了一些测试用例，它确实返回正确。但是我没有使用过 DP ......意味着它必须是这两个中的任何一个。

1. 我的功能是错误的。它没有得到 LIS。
2. 运行时间是 2^n，我只是没能正确计算运行时间。

谁能帮我理清思路？我的函数是错误的，是运行时 2^n，还是可以在没有 DP 的情况下获得 LIS？

Answer 1

它没有得到 LIS。例如，

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

返回 3。应该是 4。