最长非降子序列的N*logN解法

之前讲到过求最长非降子序列的O(N^2)解法。链接

这次在原来的基础上介绍一下N*logN解法。

该解法主要是维护一个数组minValue，minValue[i]表示最长上身子序列长度为i的数的最小值。

代码如下：

#include <iostream>

using namespace std;

#define inf (1<<29)

const int maxn = 100100;

int n, a[maxn], minValue[maxn];

int getIndex(int R, int x)

{

    int L = 0;

    while (L <= R)

    {

        int mid = (L + R) / 2;

        if (minValue[mid] < x)

            L = mid + 1;

        else

            R = mid - 1;

    }

    return L - 1;

}

int main()

{

    cin >> n;

    for (int i = 0; i < n; i ++)

        cin >> a[i];

    minValue[0] = 0;

    for (int i = 1; i <= n; i ++)

        minValue[i] = inf;

    int R = 0;

    for (int i = 0; i < n; i ++)

    {

        int idx = getIndex(R, a[i]);

        if (idx+1 > R)

            R = idx + 1;

        minValue[idx+1] = min(minValue[idx+1], a[i]);

    }

    cout << R << endl;

    return 0;

}

巴特西

最长非降子序列的N*logN解法

最新文章

热门文章