首页 > 代码库 > 从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。
从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。
题目描述：
从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。
分析：
这可以用双端LIS方法来解决，先求一遍从左到右的，再求一遍从右到左的。最后从里面选出和最大的即可。
代码实现：
#include <iostream>using namespace std;int DoubleEndLIS(int *arr, int len){ int *LIS = new int[len]; int *lefToRight = new int[len]; //leftToRight[i]表示0~i最长子序列长度-1 int *rightToLeft = new int[len]; int maxLen = 0; //记录总共的(上升+下降)最长子序列长度 int low, high, mid; for (int i = 0; i < len; ++i) { lefToRight[i] = 0; LIS[i] = 0; } LIS[0] = arr[0]; for (int i = 1; i < len; i++) { low = 0; high = lefToRight[i-1]; while (low <= high) { mid = (low + high)/2; if (LIS[mid] < arr[i]) { low = mid + 1; } else { high = mid -1; } } LIS[low] = arr[i]; if (low > lefToRight[i-1]) { lefToRight[i] = lefToRight[i-1] + 1; //最长子序列长度加1 } else { lefToRight[i] = lefToRight[i-1]; } } //leftToRight的每个值增加1，因为他们是最长子序列值-1 //此时leftToRight表示的是最长子序列的真正值。 for (int i = 0; i < len; i++) { lefToRight[i]++; } //从右到左 for (int i = 0; i < len; i++) { rightToLeft[i] = 0; LIS[i] = 0; } int k = 0; LIS[0] = arr[len-1]; for (int i = len -2; i >= 0; --i) { low = 0; high = rightToLeft[k]; while (low <= high) { mid = (low + high)/2; if (LIS[mid] < arr[i]) { low = mid + 1; } else { high = mid - 1; } } LIS[low] = arr[i]; if (low > rightToLeft[k]) { rightToLeft[k+1] = rightToLeft[k] + 1; } else { rightToLeft[k+1] = rightToLeft[k]; } ++k; } for (int i = 0; i < k; ++i) { rightToLeft[i]++; } //求最大值即为要求的 for (int i = 0; i < len; ++i) { cout<<"i: "<<i<<" "<<lefToRight[i]<<" "<<rightToLeft[len-i-1]<<endl; if (lefToRight[i] + rightToLeft[len-i-1] > maxLen) maxLen = lefToRight[i] + rightToLeft[len-i-1]; } cout<<"maxLen:"<<maxLen<<endl; delete LIS; delete lefToRight; delete rightToLeft; return len - maxLen + 1;}int main(){ int arr[] = {1,5,7,6,9,3,8,4,2}; int ret; ret = DoubleEndLIS(arr, 9); cout<<ret<<endl; return 0;}
参考：http://blog.csdn.net/nciaebupt/article/details/8466049
但是，他的程序有问题，我做了修改。
从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。