求数组中最长递增子序列

写一个时间复杂度尽可能低的程序，求一个一维数组（ N 个元素）中的最长递增子序列的长度。

例如：在序列 1 ， -1 ， 2 ， -3 ， 4 ， -5 ， 6 ， -7 中，其最长的递增子序列为 1 ， 2 ， 4 ， 6 。

分析与解法

       根据题目的要求，求一维数组中的最长递增子序列，也就是找一个标号的序列 b[0],b[1], … ,b[m](0 <= b[0] < b[1] < … < b[m] < N) ，使得 array[b[0]]<array[b[1]]< … <array[b[m]] 。

解法一

       根据无后效性的定义我们知道，将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态来说，它以前各阶段的状态无法直接影响它未来的决策，而只能间接地通过当前的这个状态来影响。换句话说，每个状态都是历史的一个完整总结。

       同样的，仍以序列 1 ， -1 ， 2 ， -3 ， 4 ， -5 ， 6 ， -7 为例，我们在找到 4 之后，并不关心 4 之前的两个值具体是怎样，因为它对找到 6 没有直接影响。因此，这个问题满足无后效性，可以通过使用动态规划来解决。

       可以通过数字的规律来分析目标串： 1 ， -1 ， 2 ， -3 ， 4 ， -5 ， 6 ， -7 。

       使用 i 来表示当前遍历的位置

       当 i=1 时，显然，最长的递增序列为（ 1 ），序列长度为 1.

       当 i=2 是，由于 -1<1 。因此，必须丢弃第一个值后重新建立串。当前的递增序列为（ -1 ），长度为 1 。

       当 i=3 时，由于 2>1,2>-1 。因此，最长的递增序列为（ 1,2 ） ,(-1,2), 长度为 2 。在这里， 2 前面是 1 还是 -1 对求出后面的递增序列没有直接影响。（但是在其它情况下可能有影响 ）

       依此类推之后，我们得出如下的结论。

       假设在目标数组 array[] 的前 i 个元素中，最长递增子序列的长度为 LIS[i] 。那么，

       LIS[i+1]=max{1,LIS[k]+1},array[i+1]>array[k],for any k <= i

即如果 array[i+1] 大于 array[k], 那么第 i+1 个元素可以接在 LIS[k] 长的子序列后面构成一个更长的子序列。于此同时 array[i+1] 本身至少可以构成一个长度为 1 的子序列。

       根据上面的分析，就可以得到代码清单

这种方法的时间复杂度为O(N² + N) = O(N² )

 #include <stdio.h>#include <stdlib.h>int main(int argc, char **argv){ time_t start = time(NULL); int b[100000]; char *filename; FILE *fin; int n, a[100000]; int i, j, k; int max; if(argc != 2) { printf("usage: ./lis TEST_FILE_NAME/n"); return 1; } filename = argv[1]; printf("input file: %s/n", filename); fin = fopen(filename, "r"); if(fin == NULL) { printf("file open error./n"); return 1; } fscanf(fin, "%d", &n); for(i = 0; i < n; ++i) { fscanf(fin, "%d", &a[i]); } printf("n: %d, a[n-1]: %d/n", n, a[n-1]); /* for(i = 0; i < n; ++i) { printf("%d/t", a[i]); } printf("/n"); */ for(i = 0; i < n; ++i) { max = 0; for(k = 0; k < i; ++k) { if(a[k] < a[i] && b[k] > max) max = b[k]; } b[i] = max + 1; } max = 0; for(i = 0; i < n; ++i) { if(b[i] > max) max = b[i]; } printf("max: %d/n", max); printf("total time used: %ld seconds./n", time(NULL) - start); return 0;}  

解法二

    在前面的分析中，当考察第i+1 个元素的时候，我们是不考虑前面i 个元素的分布情况的。现在我们从另一个角度分析，即当考察第i+1 个元素的时候考虑前面i 个元素的情况。

    对于前面i 个元素的任何一个递增子序列，如果这个子序列的最大的元素比array[i+1] 小，那么就可以将array[i+1] 加在这个子序列后面，构成一个新的递增子序列。

    比如当i=4 的时候，目标序列为 1 ， -1 ， 2 ， -3 ， 4 ， -5 ， 6 ， -7 最长递增序列为 (1,2),(-1,2) 。

       那么，只要 4>2, 就可以把 4 直接增加到前面的子序列中形成一个新的递增子序列。

       因此，我们希望找到前 i 个元素中的一个递增子序列，使得这个递增子序列的最大的元素比 array[i+1] 小，且长度尽量地长。这样将 array[i+1] 加在该递增子序列后，便可以找到以 array[i+1] 为最大元素的最长递增子序列。

       仍然假设在数组的前 i 个元素中，以 array[i] 为最大元素的最长递增子序列的长度为 LIS[i] 。

       同时，假设：

       长度为 1 的递增子序列最大元素的最小值为 MaxV[1];

       长度为 2 的递增子序列最大元素的最小值为 MaxV[2];

       ……

       长度为 LIS[i] 的递增子序列最大元素的最小值为 MaxV[LIS[i]];

本循环不变式 P 是：

       P ： k 是序列 a[0:i] 的最长递增子序列的长度， 0 ≤i ＜n 。

    容易看出，在由i-1 到i 的循环中，a[i] 的值起关键作用。如果a[i] 能扩展序列a[0;i-1] 的最长递增子序列的长度，则k=k+1 ，否则k 不变。设a[0;i-1] 中长度为k 的最长递增子序列的结尾元素是a[j](0 ≤j ≤i-1) ，则当a[i] ≥a[j] 时可以扩展，否则不能扩展。如果序列a[0;i-1] 中有多个长度为k 的最长递增子序列，那么需要存储哪些信息？容易看出，只要存储序列a[0;i-1] 中所有长度为k 的递增子序列中结尾元素的最小值b[k] 。因此，需要将循环不变式P 增强为：

    P ：0 ≤i ＜n;k 是序列a[0;i] 的最长递增子序列的长度；

    b[k] 是序列a[0;i] 中所有长度为k 的递增子序列中最小结尾元素值。

    相应地，归纳假设也增强为：已知计算序列a[0;i-1](i ＜n) 的最长递增子序列的长度k 以及序列a[0;i] 中所有长度为k 的递增子序列中的最小结尾元素值b[k] 的正确算法。

    增强归纳假设后，在由i-1 到i 的循环中，当a[i] ≥b[k] 时，k=k+1 ，b[k]=a[i], 否则k 值不变。注意到当a[i] ≥b[k] 时，k 值增加，b[k] 的值为a[i] 。那么，当a[i] ＜b[k] 时，b[l;k] 的值应该如何改变？如果a[i]<b[l], 则显然应该将b[l] 的只改变为a[i], 当b[l] ≤a[i] ≤b[k] 时，注意到数组b 是有序的，可以用二分搜索算法找到下标j ，使得b[j-1] ≤a[i] ≤b[j] 。此时，b[1;j-1] 和b[j+1;k] 的值不变，b[j] 的值改变为a[i] 。

#include <stdio.h>#include <stdlib.h>#include <sys/time.h>int b[100000];int binary_search(int i, int start, int end){ if(start > end) return start; int mid = (start + end) / 2; if(b[mid] > i) { return binary_search(i, start, mid - 1); } else { return binary_search(i, mid + 1, end); }}int main(int argc, char **argv){ //time_t start = time(NULL); //struct timeval tv; char *filename; FILE *fin; int n, a[100000]; int i, j, k; //gettimeofday(&tv, NULL); //suseconds_t start = tv.tv_usec; //printf("start: %ld/n", start); //sleep(2); if(argc != 2) { printf("usage: ./lis TEST_FILE_NAME/n"); return 1; } filename = argv[1]; printf("input file: %s/n", filename); fin = fopen(filename, "r"); if(fin == NULL) { printf("file open error./n"); return 1; } fscanf(fin, "%d", &n); for(i = 0; i < n; ++i) { fscanf(fin, "%d", &a[i]); } //printf("n: %d, a[n-1]: %d/n", n, a[n-1]); /* for(i = 0; i < n; ++i) { printf("%d/t", a[i]); } printf("/n"); */ k = 1, b[1] = a[0]; for(i = 1; i < n; ++i) { if(a[i] == b[k]) { continue; } else if(a[i] > b[k]) { k += 1; b[k] = a[i]; } else if(a[i] < b[1]) { b[1] = a[i]; } else if(a[i] == b[1]) { continue; } else { j = binary_search(a[i], 1, k); if(b[j-1] != a[i]) b[j] = a[i]; } } printf("k: %d/n", k); //gettimeofday(&tv, NULL); //suseconds_t now = tv.tv_usec; //printf("now: %ld/n", now); //printf("total time used: %ld microseconds./n", now - start); //printf("total time used: %ld seconds./n", time(NULL) - start); //for(i = 1; i <= k; ++i) //{ //printf("%d/t", b[i]); //} //printf("/n"); return 0;}