HackerRank HourRank 27 : B. Maximizing the Profit

途中までは良かったのにね。
https://www.hackerrank.com/contests/hourrank-27/challenges/maximizing-the-profit

問題

N要素の整数列Pが与えられる。
i＜j＜kとなる３つの要素番号を選んだ時、P[i]*P[j]*P[k]の最大値を求めよ。

解法

Pには負の値もあるのでややこしいが、基本的には最小値か最大値を選んでおくとよい。

jを順に選んでいくことを考える。
P[k]の候補として、P[j+1]～P[N-1]のうち最大値かP[j]より大きな最小値の２通りが考えられる。
同様にP[i]の候補として、P[0]～P[j-1]のうち最小値かP[j]より小さな最大値の２通りが考えられる。

set+lower_bound等を使い上記最小値・最大値を求めていこう。
jに対しP[i],P[k]は高々２通りずつ候補があることになるので、それらを総当たりすればよい。

int N;
ll P[303030];

vector<ll> L[303030];
vector<ll> R[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	
	set<ll> S;
	FOR(i,N) {
		if(i) {
			if(*S.begin()<P[i]) L[i].push_back(*S.begin());
			auto it=S.lower_bound(P[i]);
			if(it!=S.begin()) {
				it--;
				L[i].push_back(*it);
			}
		}
		S.insert(P[i]);
	}
	
	S.clear();
	for(i=N-1;i>=0;i--) {
		if(i!=N-1) {
			auto it=S.lower_bound(P[i]+1);
			if(it!=S.end()) R[i].push_back(*it);
			it=S.end();
			it--;
			if(*it>P[i]) R[i].push_back(*it);
		}
		S.insert(P[i]);
	}
	ll ret=-1LL<<61;
	
	FOR(i,N) {
		FORR(l,L[i]) FORR(r,R[i]) ret=max(ret,l*r*P[i]);
	}
	
	if(ret==-1LL<<61) ret=-1;
	cout<<ret<<endl;
	
}

まとめ

こういうの細かいミスが怖かったが幸い一発AC。