在读高中的时候，每天早上学校都要组织全校的师生进行跑步来锻炼身体，每当出操令吹响时，大家就开始往楼下跑了，然后身高矮的排在队伍的前面，身高较高的就要排在队尾。突然，有一天出操负责人想了一个主意，想要变换一下队形，就是当大家都从楼上跑下来后，所有的学生都随机地占在一排，然后出操负责人从队伍中抽取出一部分学生，使得队伍中剩余的学生的身高从前往后看，是一个先升高后下降的“山峰”形状。据说这样的形状能够给大家带来好运，祝愿大家在学习的道路上勇攀高峰。(注，山峰只有一边也符合条件，如1,1、2,2、1均符合条件)
思路
1. 这道题我还蛮想总结一下, 因为与之类似的一道题 Candy 当时就把我做崩溃了. 并且, Leetcode 上买卖股票问题和这个也很类似.
2. 这道题实际上比买卖股票还有简单些. 买卖股票从左到右需要 dp 一遍, 从右到左还需要一遍 dp, 并且函数需要各写各的, 因为我们需要求解的是从左向右上升的序列, 而这道题计算的是两个序列, 分别是从左到右递增和从右到左递增. 这样的话先计算从左到右的, 然后 reverse 数组, 再计算一遍又从右到左的即可, 函数只需要写一个.
3. 写完 LIS, 最后就要讨论边界了. 题目说 11, 22, 1 都算有效的, 但第二个案例却返回 4 , 有些纠结.
代码 未通过九度测试
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std; int longest1[];
int longest2[]; int height[]; int record1[];
int record2[]; int search(int x, int n, int *record) {
int low = , high = n-; while(low <= high) {
int mid = (low+high)>>; if(record[mid] == x) {
return mid;
}else if(record[mid] > x) {
high = mid -;
}else{
low = mid + ;
}
}
return low;
} void lt2rt(int n, int *record, int *longest, int first) {
int len = ;
record[] = first;
longest[] = ;
for(int i = ; i < n; i ++) {
if(height[i] > record[len-]) {
record[len] = height[i];
len++;
}else{
int pos = search(height[i], len, record);
record[pos] = height[i];
}
longest[i] = len;
}
} int main() { int n;
while(scanf("%d", &n) != EOF) {
for(int i = ; i < n; i ++)
scanf("%d", height+i); lt2rt(n, record1, longest1, height[]); reverse(height, height+n);
lt2rt(n, record2, longest2, height[n-]); int maxnum = ;
for(int i = ; i < n-; i ++) {
int left = longest1[i];
int right = longest2[n-i-];
maxnum = max(maxnum, left+right);
}
maxnum = max(maxnum, longest2[n-]);
maxnum = max(maxnum, longest1[n-]); cout << n-maxnum << endl;
}
return ;
}