PAT A1101

这道题的题目和之前的PAT题目相同，也是采用打表的方法；先预先算好所有的元素；建立两个数组，left，right；left从左到右遍历，索引index装从左到index中最大的元素；right从右到左遍历，索引index装从右到index中最小元素；之后从0~n比较left，right相应的成员，也就是看左边最大和右边最小是否符合题目规范#include<iostream>#include<stdlib.h>#include<stdio.h>using namespace std;const int maxn=100010;const int INF=0x3fffffff;int data[maxn];int left1[maxn];int right1[maxn];int ans[maxn];int num=0;int n;int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&data[i]); } left1[0]=0; for(int i=1;i<n;i++){ left1[i]=max(left1[i-1],data[i-1]); } right1[n-1]=INF; for(int i=n-2;i>=0;i–){ right1[i]=min(right1[i+1],data[i+1]); } for(int i=0;i<n;i++){ if(left1[i]<data[i]&&right1[i]>data[i]){ ans[num++]=data[i]; } } printf("%d\n",num); for(int i=0;i<num;i++){ printf("%d",ans[i]); if(i<num-1) printf(" “); } printf("\n”); system(“pause”); return 0;}