首页 > 代码库 > 从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的

从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的

2024-07-23 19:42:09   219人阅读

问题：从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。

解法：这是双端 LIS 问题，用 DP 的思想可解，目标规划函数 max{ b[i] + c[i] }, 其中 b[i] 为从左到右， 0 ~ i 个数之间满足递增的数字个数； c[i] 为从右到左， n-1 ~ i 个数之间满足递增的数字个数。最后结果为 n - max + 1。其中 DP 的时候，可以维护一个 inc[] 数组表示递增数字序列，inc[i] 为从小到大第 i 大的数字（这句话还可以这么理解，inc[i]表示递增序列长度为i时的最小末尾数，关于这个的理解还可以看上面关于最长递减子序列的分析），然后在计算 b[i] c[i] 的时候使用二分查找在 inc[] 中找出区间 inc[0] ~ inc[i-1] 中小于 a[i] 的元素个数（low）。

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

[cpp] view plaincopy
  1. /**  
  2. * The problem:  
  3. * 从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。  
  4. * use binary search, perhaps you should compile it with -std=c99  
  5. * fairywell 2011  
  6. */    
  7. #include <stdio.h>    
  8.     
  9. #define MAX_NUM    (1U<<31)    
  10.     
  11. int    
  12. main()    
  13. {    
  14.     int i, n, low, high, mid, max;    
  15.         
  16.     printf("Input how many numbers there are: ");    
  17.     scanf("%d/n", &n);    
  18.     /* a[] holds the numbers, b[i] holds the number of increasing numbers  
  19.     * from a[0] to a[i], c[i] holds the number of increasing numbers  
  20.     * from a[n-1] to a[i]  
  21.     * inc[] holds the increasing numbers  
  22.     * VLA needs c99 features, compile with -stc=c99  
  23.     */    
  24.     double a[n], b[n], c[n], inc[n];    
  25.         
  26.     printf("Please input the numbers:/n");    
  27.     for (i = 0; i < n; ++i) scanf("%lf", &a[i]);    
  28.         
  29.     // update array b from left to right    
  30.     for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;    
  31.     //b[0] = 0;    
  32.     for (i = 0; i < n; ++i) {    
  33.         low = 0; high = i;    
  34.         while (low < high) {    
  35.             mid = low + (high-low)*0.5;    
  36.             if (inc[mid] < a[i]) low = mid + 1;    
  37.             else high = mid;    
  38.         }    
  39.         b[i] = low + 1;    
  40.         inc[low] = a[i];    
  41.     }    
  42.         
  43.     // update array c from right to left    
  44.     for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;    
  45.     //c[0] = 0;    
  46.     for (i = n-1; i >= 0; --i) {    
  47.         low = 0; high = i;    
  48.         while (low < high) {    
  49.             mid = low + (high-low)*0.5;    
  50.             if (inc[mid] < a[i]) low = mid + 1;    
  51.             else high = mid;    
  52.         }    
  53.         c[i] = low + 1;    
  54.         inc[low] = a[i];    
  55.     }    
  56.         
  57.     max = 0;    
  58.     for (i = 0; i < n; ++i )    
  59.         if (b[i]+c[i] > max) max = b[i] + c[i];    
  60.         printf("%d number(s) should be erased at least./n", n+1-max);    
  61.         return 0;    
  62. }   

从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的


联系
我们