解题思路：这题的本质就是：求一个给定的数字序列中，非递增（或非递减）子序列的最少的条数。
思维误区：本题很容易被样例坑，以为是直接求跳跃点（i < j && ai < aj）的个数 + 1。其实，从样例本身来看，确实有这个嫌疑。不过不难想到8 500 300 400 200 80 200 100 50这样测试样例，明显地，如果求跳跃点的个数，这里有2个跳跃点，结果是3。但是，可以看出，子序列500 400 200 200 100 50和子序列300 80才是符合题目要求的，结果应该是2。
自编测试样例：
8 389 207 155 300 299 170 158 65 1 100 6 300 200 400 200 100 500 8 500 300 400 200 300 100 200 50 8 500 300 400 200 80 200 100 50 8 500 300 400 200 80 500 100 50
AC代码：
#includeusing namespace std;vector nums;int n;void solve() { vector dp; for(int i = 0;i < n;i++)dp.push_back(1); for(int i = 0;i < n;i++){ for(int j = 0;j < i;j++){ if(nums[i] > nums[j])dp[i] = max(dp[i], dp[j] + 1); } } int res = 0; for(int i = 0;i < n;i++)res = max(res, dp[i]); printf("%d\n", res);}int main() { //freopen("probCTDS.txt","r",stdin); int h; while(scanf("%d", &n) != EOF) { nums.clear(); for(int i = 0; i < n; i++) { scanf("%d", &h); nums.push_back(h); } solve(); } return 0;}
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
实际上，既然是求非递增子序列的最少的条数，那么，反过来想，就是求最长递增子序列的长度。为什么？因为在递增子序列中，每一个元素都是非递增子序列的开头元素。在求非递增子序列的最少的条数的时候，每次遇到最长递增子序列一个元素，就应该新起一个序列。是吧。
所以，可以优化算法，得到如下核心算法代码：
void solve(){ fill(dp, dp + n, INF); for(int i = 0;i < n;i++)*lower_bound(dp, dp + n, a[i]) = a[i]; printf("%d\n", lower_bound(dp, dp + n, INF) - dp);}为什么这样是对的呢？因为在求最长递增子序列的过程中，递增子序列的最后一个值越小，这个递增子序列越有利。 举个栗子：
数字序列为：1 3 5 7 9 2 4 6 8 10
对于上述算法，当i=4(对应的数字为9)时，dp中的值为：1 3 5 7 9 INF................
i++, i = 5(nums[i] = 2), 二分搜索dp, dp中>=2的元素就是3，位置为1，那么，2替换原来dp数组中的3。
同样，4就替换原来dp数组中的5。在此过程中可以发现，更小的元素会把更大的元素替换掉，使得后面的数字更有利。
注意：我们用这个算法求的的最长递增子序列的长度，求出的dp数组的值不一定是最长递增子序列。
比如：数组序列：1 3 5 7 9 2 4 6
最长递增子序列的长度为5，dp数组的值为：1 2 4 6 9。这显然不是最长递增子序列。但是，这个序列的长度确实是最长递增子序列的长度。
如果不清楚lower_bound和upper_bound函数的用法，请自行查找并掌握它们。