BOJ 10885 수열의 장인

문제 링크입니다.

관찰

수열의 구간 곱의 최댓값을 구해야 합니다. 그런데 이제 원소가 -2, -1, 0, 1, 2 밖에 없는.

수열에 0이 있으면 일단 최댓값은 0 이상입니다. 0을 곱하면 뭐가 어찌 됐든 구간 곱은 0이 되는 거니까, 굳이 더 곱해볼 필요가 없겠네요. 수열을 0을 기준으로 다 쪼개버렸다고 생각합시다.

남은 1, -1, 2, -2는 곱했을 때 구간 곱의 절댓값을 감소시키지 않습니다.

원소가 달랑 하나 있고 그게 음수인 게 아닌 이상 답이 음수일 일은 없고, 문제 조건에 의해 N ≥ 2 입니다.

구간 길이 늘리기

절댓값이 감소하지 않는다는 보장이 있으니 그냥 일단 곱해 보고, 그러다가 부호가 (+)가 되었을 때만 최댓값을 갱신하면서 넘어가도 좋습니다. 0이 나오면 여태까지 곱했던 걸 싹 날리고 그다음 수부터 다시 곱해나가면 됩니다.

이때 0으로 감싸진 어떤 수열 조각의 전체 곱이 (-)라고 해 봅시다. 일단 구간이 클수록 절댓값의 측면에서 불리할 게 없으니, 이 수열 조각 안에서 구간 곱의 최댓값이 나올 수 있는 케이스는 첫 음수 원소까지를 제외한 오른쪽 구간과 마지막 음수 원소까지를 제외한 왼쪽 구간으로 충분합니다. 이런 경우가 나타날 때마다 따로 처리하는 것도 가능하겠지만, 귀찮으니 그냥 왼쪽으로 통일해서 구하고 나중에 수열을 통째로 뒤집어서 똑같이 한 번 더 계산하는 것으로 충분합니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int a[303030];
const ll mod = 1e9+7;

ll pw(ll n, ll r){
	ll ret = 1;
	while(r){
		if(r&1) ret = ret*n%mod;
		n = n*n%mod;
		r>>=1;
	}
	return ret;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int T; cin >> T; while(T--){
		int n; cin >> n;
		int mx = -3, mxcnt = -1, cnt[2] = {0, 0}, minus = 0, minustwo = 0;
		bool flag = 0;
		for(int i = 0; i < n; i++){
			cin >> a[i]; int& k = a[i];
			mx = max(mx, k);
			if(k > 0) flag = 1;
			if(k > 1) cnt[minus]++;
			if(k < 0) minus++;
			if(k < -1) minustwo++;
			if(minus == 2){
				flag = 1;
				cnt[0] += minustwo+cnt[1];
				cnt[1] = minustwo = minus = 0;
			}
			if(flag) mxcnt = max({mxcnt, cnt[0], cnt[1]});
			if(!k) flag = cnt[0] = cnt[1] = minus = minustwo = 0;
		}
		if(mxcnt < 0){
			cout << mx << '\n'; continue;
		}
		cnt[0] = cnt[1] = 0; minus = 0; minustwo = 0;
		flag = 0;
		for(int i = 0; i < n; i++){
			int& k = a[n-i-1];
			if(k > 0) flag = 1;
			if(k > 1) cnt[minus]++;
			if(k < 0) minus++;
			if(k < -1) minustwo++;
			if(minus == 2){
				flag = 1;
				cnt[0] += minustwo+cnt[1];
				cnt[1] = minustwo = minus = 0;
			}
			if(flag) mxcnt = max({mxcnt, cnt[0], cnt[1]});
			if(!k) flag = cnt[0] = cnt[1] = minus = minustwo = 0;
		}
		cout << pw(2, mxcnt) << '\n';
	}
}