给出一个序列,求非下降序列最大长度,或非上升序列最大长度

首先看一下时间复杂度为 O(n*n) 的一维递推算法
这里给出一个序列,

原始序列
原始序列

第一行为原序列,第二行,代表第一个数字到此为止最大递增序列长度

我们来解释一下第二行数字 T 怎么推的:
T1 :本身数字长度就是 1 ,如果只有一个字符那么最大长度就是 1
T2 :由于 2 > 1 ,所以取 K1 状态的解再加上本身长度 1 ,然后取最大值,K1 前面没数了,所以继续往后走
T3 :4 > 2 ,继续取 K2 状态的解加 1 在比较取最大值得 3 ,此时还要再比较 K1 值,同理 4 > 1 ,取 K1 状态的解加 1 和之前比较好的 3 取最大值,得 3 还是最大的,所以 K4 这个状态最大递增序列为 3
.
.
.
到了 K6 ,也就是到第六个数时,3 < 7 ,继续向前比较知道 3 > 2 ,取 T2 加 1 比较再取最大值。
.
就这样每一轮都要和前面所有数比较才能得出最终结果;
代码如下:时间复杂度 O(n*n)

int Dp(int a[], int n) {
    int MAX_long = 0;
    int long_dp[100005];
    long_dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = i - 1; j >= 1; j--) {
            if (a[i] > a[j]) {
                long_dp[i] = max(long_dp[i], long_dp[j] + 1);
            }
        }
        MAX_long = max(MAX_long, long_dp[i]);
    }
    return MAX_long;
}

我们再来看看时间复杂度为 O(nlogn)
这个算法首先需要建立数组 b[] ,这个数组是用来干嘛的呢?就是用来储存最长的递增序列的。


上面图代表我们如何一个一个插入数组 b[] ,首先插入第一个数,因为本身就是一个长度为 1 的序列,再插入 2 ,2 > 1 ,直接将他插入末尾,同理一直到 7 ,此时数组为 1 ,2 ,4 ,6 ,7 ,说明截至 7 这个位置,最大长度为 5 ,且最大长度序列为:1 ,2 ,4 ,6 ,7
当再次插入 7 后边的 3 时,3 < 7 ,那么这个时候怎么办?我们寻找 3 以前的 比自己大的最小的数 也就是 4 这个数,在进行替换,我们为什么替换呢?
因为截至 7 为止最大长度为 5 ,我们将 4 替换以后并不影响之前每个数字之下的最大长度,而且也得到了 3 这个数字对应的最大长度为 3 ,序列为 1 ,2 ,3 。这样做的目的是为了,不能排除整个数字串最终结果里面不会包含这个 3 ,一个小的数在前边,当然比一个大的数在前边更有可能找出最长序列
同理 4 ,5 替换 6 ,7
6 ,9 再加入 5 的后边,此时的 b[] 数组长度就是最大序列长度

int LNDS(int n, int a[]) {
    int b[100005];
    int val = 1;
    b[val] = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] > b[val]) {
            b[++val] = a[i];
        } else {
            int t = lower_bound(b + 1, b + val + 1, a[i]) - b;
            b[t] = a[i];
        }
    }
    return val;
}

本问题中 b[] 数组本身就是一个非递减数组 upper_bound() 以及 lower_bound() 函数前提条件为传入i到j地址中的数为非递减,也就是传入的区间必须为排序好的

代码中函数:
upper_bound(i,j,key) 表示从 i 地址到 j ( 不包括 j ) 地址查找第一个比自己大的数,返回这个数的地址

lower_bound(i,j,key) 表示从 i 地址到 j ( 不包括 j ) 地址查找第一个比自己大或者等于的数,返回这个数的地址

如果这个问题是非下降最大序列长度,我们就要使用 upper_bound() 方法,保留相等的数使长度变大!

此代码时间复杂度为O(nlogn)