[关闭]
@natsumi 2017-03-24T03:26:33.000000Z 字数 3991 阅读 1864

最长不下降子序列

Algorithms


题目

给出长度为n的数组a,求出其最长不下降子序列的长度。比如n=5,5个数是{4,6,5,7,3},其最长不下降子序列就是{4,6,7},长度为3。

O(n^2)算法

思路

当我们定义问题F(i)为以a[i]结束的最长不下降子序列时(这个子序列的最后一项是a[i]),则问题F(i)有i个子问题:F(0), F(1), …, F(i-1)。

我们要使F(i)最长,则要在满足0 <= j < ia[j] < a[i]条件的j中,找到使得F(j)最大的j,此时这时F(i)=F(j)+1。

如果不存在满足0 <= j < ia[j] < a[i]条件的j,则
a[i]不存在前驱节点,那么F(i)=1。

最后从F(0)~F(a.length-1),找出最大值就是最长不下降子序列长度。

代码

  1. /**
  2. * 最长不下降子序列 o(n^2)
  3. *
  4. * @param a 待查序列
  5. * @return 最长不下降子序列长度
  6. */
  7. public static int longestIncreasingSubseq1(int a[]) {
  8. int[] len = new int[a.length];
  9. int i, j;
  10. for (i = 0; i < a.length; i++) { //每次循环就确定了前i项中的最长不下降子序列的长度并存放在num[i]中.
  11. len[i] = 1;
  12. for (j = 0; j < i; j++) {
  13. if (a[j] <= a[i] && len[j] + 1 > len[i]) //找出当前的前驱节点 并更新长度.
  14. len[i] = len[j] + 1;
  15. }
  16. }
  17. int max = 0;
  18. for (i = 0; i < a.length; i++)
  19. if (max < len[i])
  20. max = len[i];
  21. return max;
  22. }

O(nlogn)算法

简洁的讲解

建立了一个数组(这里假设为d[]),那么d[i]表示读到当前数据的时候(这个d[]是每读入题目数组的一个元素的时候就更新一次)长度为i的严格???单增序列中结尾元素的最小值,用t来表示当前d[]数组的长度,那么当题目数组全部读完后,t的值就是最长不下降子序列长度

具体点来讲:

设当前的已求出来的长度为t,则判断a[i]和d[t];

更详细清楚的讲解

来自http://www.cnblogs.com/itlqs/p/5743114.html

定义:a[1..n]为原始序列,d[k]表示长度为k的不下降子序列末尾元素的最小值,len表示当前已知的最长子序列的长度。

初始化:d[1]=a[1]; len=1;(0个元素的时候特判一下)

现在我们已知最长的不下降子序列长度为1,末尾元素的最小值为a[1],那么我们让i从2到n循环,依次求出前i个元素的最长不下降子序列的长度,循环的时候我们只需要维护好d这个数组还有len就可以了。

关键问题就是怎么维护?

可以看出我们是要用logn的复杂度维护的。实际上利用了d数组的一个性质:单调不减性。(长度更长了,d[k]的值是不会减小的)

考虑新进来一个元素a[i]:

如果这个元素大于等于d[len],直接让d[len+1]=a[i],然后len++。这个很好理解,当前最长的长度变成了len+1,而且d数组也添加了一个元素。

如果这个元素小于d[len]呢?说明它不能接在最后一个后面了。那我们就看一下它该接在谁后面。

准确的说,并不是接在谁后面。而是替换掉谁。因为它接在前面的谁后面都是没有意义的,再接也超不过最长的len,所以是替换掉别人。

那么替换掉谁呢?就是替换掉那个最该被它替换的那个。也就是在d数组中第一个大于它的。第一个意味着前面的都小于等于它。

假设第一个大于它的是d[j],说明d[1..j-1]都小于等于它,那么它完全可以接上d[j-1]然后生成一个长度为j的不下降子序列,而且这个子序列比当前的d[j]这个子序列更有潜力(因为这个数比d[j]小)。所以就替换掉它就行了,也就是d[j]=a[i]。

其实这个位置也是它唯一能够替换的位置(前面的替了不满足d[k]最小值的定义,后面替换了不满足不下降序列)

至于第一个大于它的怎么找……STL upper_bound。每次复杂度logn。

至此,我们就神奇的解决了这个问题。

代码

  1. /**
  2. * 最长不下降子序列 o(nlogn)
  3. *
  4. * @param a 待查序列
  5. * @return 最长不下降子序列长度
  6. */
  7. public static int longestIncreasingSubseq2(int[] a) {
  8. if (a.length == 0) {//0个元素特判一下
  9. return 0;
  10. }
  11. int[] d = new int[a.length + 1];
  12. d[1] = a[0];//初始化
  13. int len = 1;
  14. for (int i = 1; i < a.length; i++) {
  15. if (a[i] >= d[len]) {
  16. d[++len] = a[i]; //如果可以接在len后面就接上
  17. } else {//否则就找一个最该替换的替换掉
  18. //d[len]>a[i],可以确保d[1]~d[len]中存在大于等于a[i]的元素
  19. int j = binarySearch(d, a[i], 1, len);//找到第一个大于它的d的下标
  20. d[j] = a[i];
  21. }
  22. }
  23. return len;
  24. }
  25. /**
  26. * 在数组中查找第一个大于a的元素下标
  27. * 或者等于a的某个元素下标
  28. * 注意:需保证left和right不超出d的下标范围,且d中存在大于等于a的数
  29. *
  30. * @param d 待查找数组
  31. * @param a 要查找的元素
  32. * @param left 数组中的查找范围下限
  33. * @param right 数组中的查找范围上限
  34. * @return
  35. */
  36. private static int binarySearch(int[] d, int a, int left, int right) {//定义二分查找函数
  37. int mid;
  38. while (left <= right) {
  39. mid = (left + right) / 2;
  40. if (d[mid] == a) {
  41. left = mid;
  42. return left;
  43. } else if (d[mid] > a)
  44. right = mid - 1;
  45. else
  46. left = mid + 1;
  47. }
  48. return left;
  49. }

测试

  1. public static void main(String[] args) {
  2. //二分查找的测试
  3. int[] d = new int[]{1, 2, 3, 3, 3, 4, 6, 8, 10};
  4. System.out.println(binarySearch(d, 3, 1, 4));
  5. System.out.println(binarySearch(d, 7, 0, 10));
  6. System.out.println(binarySearch(d, 10, 0, 10));
  7. System.out.println(binarySearch(d, 3, 5, 5));
  8. //当d[left]和d[right]之间不存在大于或者等于a的数,输出会有问题
  9. System.out.println(binarySearch(d, 10, 5, 5));
  10. System.out.println();
  11. //最长不下降子序列测试
  12. int[] a = new int[]{3, 18, 7, 14, 10, 12, 23, 41, 16, 24};
  13. System.out.println(longestIncreasingSubseq1(a));
  14. System.out.println(longestIncreasingSubseq2(a));
  15. a = new int[]{1, 2, 3, 4, 5};
  16. System.out.println(longestIncreasingSubseq1(a));
  17. System.out.println(longestIncreasingSubseq2(a));
  18. a = new int[]{1, 2, 2, 1, 2, 2};
  19. System.out.println(longestIncreasingSubseq1(a));
  20. System.out.println(longestIncreasingSubseq2(a));
  21. a = new int[0];
  22. System.out.println(longestIncreasingSubseq1(a));
  23. System.out.println(longestIncreasingSubseq2(a));
  24. }

严格递增的子序列 怎么办?

仍然考虑新进来一个元素a[i]:

如果这个元素大于d[len],直接让d[len+1]=a[i],然后len++。这个很好理解,当前最长的长度变成了len+1,而且d数组也添加了一个元素。

如果这个元素等于d[len],由于我们要找的是严格递增的子序列,我们维护的数组d[len]也是严格单增的,由于说明没有比它大的元素,替换d[len]也没有意义(因为相等)。

如果这个元素小于d[len]呢?我们就看一下它该替换掉谁。

还是就是在d数组中第一个大于它的。第一个意味着前面的都小于它。假设第一个大于等于它的是d[j],说明d[1..j-1]都小于它,那么它完全可以接上d[j-1]然后生成一个长度为j的上升子序列,而且这个子序列比当前的d[j]这个子序列更有潜力(因为这个数比d[j]小)。所以就替换掉它就行了,也就是d[j]=a[i]。其实这个位置也是它唯一能够替换的位置(前面的替了不满足d[k]最小值的定义,后面替换了不满足上升序列)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注