Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2113325
  • 博文数量: 249
  • 博客积分: 1305
  • 博客等级: 军士长
  • 技术积分: 4733
  • 用 户 组: 普通用户
  • 注册时间: 2011-12-17 10:37
个人简介

不懂的东西还有很多,随着不断的学习,不懂的东西更多,无法消灭更多不懂的东西,那就不断的充实自己吧。 欢迎关注微信公众号:菜鸟的机器学习

文章分类

全部博文(249)

文章存档

2015年(1)

2014年(4)

2013年(208)

2012年(35)

2011年(1)

分类: C/C++

2013-06-05 17:24:39


问题描述:
    从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的。

解题思路:
    假设一个数组arr[n],它的分段点是i(0-i递增,i到n-1递减),假设我们用方法LIS(i)(最长递增子序列)找到从0到i的递增子序列,LDS找到从i到n-1的最长递减子序列,那么它的总长度为LIS(i) + LDS(i) - 1,所以我们扫描整个数组,即让i从0到n-1,找出使LIS(i) + LDS(i) - 1最大的即可。

    下面先讲解最长递增子序列的求解方法。
(1)动态规划
    以i结尾的序列的最长递增子序列和其[0, i - 1]“前缀”的最长递增子序列有关,设LIS[i]保存以i结尾的最长递增子序列的长度:
    若i = 0,则LIS[i] = 1;
    若i > 0,则LIS[i]的值和其[0, i - 1]前缀的最长递增子序列长度有关,用j遍历[0, i - 1]得到其最长递增子序列为LIS[j],对每一个LIS[j],如果序列array[j]  < array[i]并且LIS[j] + 1 > LIS[i],则LIS[i]的值变成LIS[j] + 1。即:
    LIS[i] = max{1, LIS[j] + 1},其中array[i] > array[j] 且 j = [0, i - 1]。
    代码如下所示。
  1. int MAX(int *LIS,int len)
  2. {
  3.     int max = 0;
  4.     for(int i = 0;i < len;++i)
  5.     {
  6.         cout<<i<<" "<<LIS[i]<<endl;
  7.         if(LIS[i] > max)
  8.             max = LIS[i];
  9.     }
  10.     return max;
  11. }

  12. int LIS(int *array,int len)
  13. {
  14.     int *LIS = new int[len];//用于记录当前各元素作为最大元素的最长递增序列长度
  15.     for(int i = 0;i < len;++i)
  16.     {
  17.         LIS[i] = 1;//设置当前元素array[i]作为最大元素的最长递增序列长度为1
  18.         for(int j = 0; j < i;++j)
  19.         {
  20.             if(array[i] > array[j] && LIS[j] + 1 > LIS[i])
  21.             {
  22.                 LIS[i] = LIS[j] + 1;
  23.             }
  24.         }
  25.     }
  26.     int res = MAX(LIS,len);
  27.     delete LIS;
  28.     return res;//获得LIS中的最大值并返回;
  29. }
(2)二分查找+动态规划实现
    假设存在一个序列d[1...9] = 2 1 5 3 6 4 8 9 7,可以看出它的LIS长度是5。
    下面一步一步试着找到它。
    我们定义一个序列B,然后令i = 1 to 9逐个考察这个序列。
    此外,我们用一个变量len来记录现在的最长算到多少。
    首先,把d[1]有序的放到B中,令B[1] = 2,就是说当只有一个数字2的时候,长度为1的LIS的最小末尾是2,这时len = 1;
    然后,把d[2]有序的放到B中,令B[1] = 1,就是说长度为1的LIS的最小末尾是1,d[1] = 2已经没用了,很容易理解吧,这时len = 1;
    接着,d[3] = 5,d[3] > B[1],所以令B[1 + 1] = B[2] = d[3] = 5,就是说长度为2的LIS的最小末尾是5,很容易理解吧,这时B[1...2] = 1, 5,len = 2;
    再来,d[4] = 3,它正好在1,5之间,放在1的位置显然不合适,因为1小于3,长度为1的LIS最小末尾应该是1,这样很容易推知,长度为2的LIS最小末尾是3,于是可以把5淘汰掉,这时B[1...2] = 1,3,len = 2;
    继续,d[5] = 6,它在3的后面,因为B[2] = 3,而6在3后面,于是很容易推知B[3] = 6,这时B[1...3] = 1,3,6,还是很容易理解吧?这时len = 3;
    第6个,d[6] = 4,你看它在3和6之间,于是就可以把6替换掉,得到B[3] = 4。B[1...3] = 1,3,4,这时len = 3;
    第7个,d[7] = 8,它很大,比4大,于是B[4] = 8,这时len = 4;
    第8个,d[8] = 9,得到B[5] = 9,len继续增大,这时len = 5;
    最后一个,d[9] = 7,它在B[3] = 4和B[4] = 8之间,所以我们知道,最新的B[4] = 7, B[1...5] = 1,3,4,7,9,len = 5。
    于是我们知道了LIS的长度为5。
    注意,注意。这个1,3,4,7,9不是LIS,它只是存储了对应长度LIS的最小末尾。有了这个末尾,我们就可以一个一个地插入数据。虽然最后一个d[9] = 7更新进去对于这个数组数据没有什么意义,但是如果后面再出现两个数字8和9,那么就可以把8更新到d[5],9更新到d[6],得到LIS的长度为6。
    然后应该发现一件事情了:在B中插入数据是有序的,而且进行替换而不需要移动——也就是说,可以使用二分查找,将每一个数字的插入时间优化到O(logn),于是算法的时间复杂度就降低到了O(nlogn)了。
    代码如下:
  1. int LIS(int *array,int len)
  2. {
  3.     //LIS数组中存储的是 递增子序列中最大值最小的子序列的最后一个元素(最大元素)在array中的位置
  4.     int *LIS = new int[len];
  5.     int left,mid,right;
  6.     int max=1;
  7.     LIS[0]=array[0];
  8.     for(int i = 1;i < len;++i)
  9.     {
  10.         left = 0;
  11.         right = max;
  12.         while(left <=right)
  13.         {
  14.             mid = (left+right)/2;
  15.             if(LIS[mid] < array[i])
  16.                 left = mid +1;
  17.             else
  18.                 right = mid -1;
  19.         }
  20.         LIS[left] = array[i];//插入
  21.         if(left > max)
  22.         {
  23.             max++;
  24.         }
  25.     }
  26.     delete LIS;
  27.     return max;
  28. }
    
    下面就开始实现“从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的“这个问题。
    双端LIS问题,用动态规划的思想可以解决,目标规划函数为max{B[i] + C[i] - 1},其中B[i]是从左到右的,0~i个数之间满足递增的数字个数;C[i]为从右到左的,n- 1 ~ i个数之间满足递增的数字个数。最后结果为n - max + 1,其中动态规划的时候,可以用二分查找进行处理,如上述求最长递增子序列的方法二。
    代码如下。
  1. /*
  2. *copyright@nciaebupt 转载请注明出处
  3. *问题:从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的(网易)。
  4. *比如数列1,4,3,5,6,7,2,0 删除的最少的数的个数为1
  5. *求解思路:双端LIS问题,使用动态规划的思路求解,时间复杂度O(nlog(n))
  6. */
  7. #include <cstdio>
  8. #include <iostream>

  9. using namespace std;

  10. int DoubleEndLIS(int *array,int len)
  11. {
  12.     int left,mid,right;
  13.     int max=0;
  14.     int k =0;

  15.     //LIS数组中存储的是 递增子序列中最大值最小的子序列的最后一个元素(最大元素)在array中的位置
  16.     int *LIS = new int[len];
  17.     //从左到右LIS中最长子序列中最大值最小的子序列的最后一个元素所在的位置,也就是0~i的数字序列中最长递增子序列的长度-1
  18.     int *B = new int[len];
  19.     //从右到左LIS中最长子序列中最大值最小的子序列的最后一个元素所在的位置,也就是len-1~i的数字序列中最长递增子序列的长度-1
  20.     int *C = new int[len];
  21.     //从左到右
  22.     for(int i = 0;i < len;++i)//LIS数组清零
  23.     {
  24.         B[i] = 0;
  25.         LIS[i] = 0;
  26.     }
  27.     LIS[0] = array[0];
  28.     for(int i = 1;i < len;++i)
  29.     {
  30.         left = 0;
  31.         right = B[k];
  32.         while(left <= right)
  33.         {
  34.             mid = (left + right)/2;
  35.             if(array[i] < LIS[mid])
  36.             {
  37.                 right = mid - 1;
  38.             }
  39.             else
  40.             {
  41.                 left = mid + 1;
  42.             }
  43.         }

  44.         LIS[left] = array[i];//将array[i]插入到LIS中
  45.         if(left > B[k])
  46.         {
  47.             B[k+1] = B[k] + 1;
  48.             k++;
  49.         }
  50.     }
  51.     for(int i = 0;i < k;++i)
  52.     {
  53.         B[i]++;
  54.     }
  55.     //从右到左
  56.     for(int i = 0;i < len;++i)//LIS数组清零
  57.     {
  58.         C[i] = 0;
  59.         LIS[i] = 0;
  60.     }
  61.     k = 0;
  62.     LIS[0] = array[len-1];
  63.     for(int i = len-2;i >= 0;--i)
  64.     {
  65.         left = 0;
  66.         right = C[k];
  67.         while(left <= right)
  68.         {
  69.             mid = (left + right)/2;
  70.             if(array[i] < LIS[mid])
  71.             {
  72.                 right = mid - 1;
  73.             }
  74.             else
  75.             {
  76.                 left = mid + 1;
  77.             }
  78.         }
  79.         LIS[left] = array[i];
  80.         if(left > C[k])
  81.         {
  82.             C[k+1] = C[k] + 1;
  83.             k++;
  84.         }
  85.     }
  86.     for(int i = 0;i <= k;++i)
  87.     {
  88.         C[i]++;
  89.     }

  90.     //求max
  91.     for(int i = 0;i < len;++i)
  92.     {
  93.         //cout<<B[i]<<" "<<C[i]<<endl;
  94.         if(B[i]+C[i]>max)
  95.             max=B[i] + C[i];
  96.     }

  97.     return len - max +1;
  98. }

  99. int main(int args,char ** argv)
  100. {
  101.     int array[] = {1,4,3,5,6,7,2,0};
  102.     int len = sizeof(array)/sizeof(int);
  103.     int res = DoubleEndLIS(array,len);
  104.     cout<<res<<endl;
  105.     getchar();
  106.     return 0;
  107. }


    参考:http://blog.csdn.net/wuwuwuwuwuwuwuwu/article/details/8466050
    感谢作者,感谢。








阅读(5327) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

cainiao_Li2015-04-15 10:43:39

你好,首先谢谢作者的辛勤劳作。讲解的很清楚。本人在vs2010编译器下调试,发现在二分查找和动态规划部分的代码存在问题。如果设置数组为{1,2,3,4,5}这种递增的序列,会出现bug,在最终的代码中,如果带入{1,2,5,4,3}这种不需要删除元素的数组也会有问题,希望作者能够修改一下,我再拜读一下。再次感谢作者的精彩讲解。