1048 数字加密（前缀和思想）

暴力（12分）

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
#define ll long long
int a[100010]; 
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	set<int> st;
	for(int i=0;i<n;i++){
		if(i==0 || i==n-1){
			st.insert(a[i]);
			continue;
		}
		//左边最大和右边最小
		int maxleft=*max_element(a,a+i);
		int minright=*min_element(a+i+1,a+n);
		if(maxleft < a[i] && a[i] < minright){
			st.insert(a[i]);
		}
	}
    cout << st.size() << '\n';
	set<int>::iterator it;
	for(it=st.begin();it!=st.end();){
		cout << *it;
		if(++it!=st.end()){
			cout << " ";
		}
	}
	return 0;
}

灵光一动，这不前缀和思想吗?
dp记录每个元素左边最大和右边最小。然后遍历判断一遍，时间O(n)就哦可了。
前缀和（25分）

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
#define ll long long
ll a[100010]; 
ll lMax[100010],rMin[100010];
int main(){
    int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	lMax[0]=a[0];
	for(int i=1;i<n;i++){
		lMax[i]=max(a[i-1],lMax[i-1]);
	}
	rMin[n-1]=a[n-1];
	for(int i=n-2;i>=0;i--){
		rMin[i]=min(a[i+1],rMin[i+1]);
	}
	set<ll> st;
	for(int i=0;i<n;i++){
		if(i==0){
			if(a[i]<rMin[i]){
				st.insert(a[i]);
			}
		}else if(i==n-1){
			if(a[i]>lMax[i]){
				st.insert(a[i]);
			}
		}else{
			if(a[i]>lMax[i] && a[i]<rMin[i]){
				st.insert(a[i]);
			}
		}
	}
    cout << st.size() << '\n';
    if(st.size()==0) cout << '\n';
	set<ll>::iterator it;
	for(it=st.begin();it!=st.end();){
		cout << *it;
		if(++it!=st.end()){
			cout << " ";
		}
	}
	return 0;
}