1554-A, *800

Problem - 1554A - Codeforces

 

문제

• 크기가 $n(2\leq n \leq 10^{5})$인 배열 $a_{1}a_{2}...a_{n}(1\leq a_{i} \leq 10^{6})$이 주어질때
  $\mathrm{min(a_{l}a_{l+1}...a_{r})\cdot max(a_{l}a_{l+1}...a_{r})},\ (1\leq l < r \leq 10^{5})$의 최대값을 구하라

 

$O(n)$

Claim
크기가 2인 Optimal interval $[l,\ r=l+1]$가 존재한다

$\because$
최적구간의 크기가 3이상이라고 가정하자.
구간에서 가장 큰 값을 $b$, 제일 작은 값을 $s$, 그 외의 값을 $m(s < m < b)$이라고 하자. 그러면

i) $m$이 존재하지 않는 경우
구간이 $b$와 $s$만으로 구성되어 있다. $[s,\ b],\ [b,\ s]$는 최적구간의 부분구간이고
최적해이므로 준 명제가 성립한다

ii) $m$이 존재하는 경우
가. $m$이 최적구간의 끝부분에 있는경우(ex. $[m,\ b,\ s]$)
$m$을 제외한 구간의 값이 더 커지므로 이 구간이 최적이라는 가정에 모순이다
나. $m$이 최적구간의 가운데에 있는경우(ex. $[b,\ m,\ s]$)
$s$를 제외한 구간의 값이 더 커지므로 이 구간이 최적이라는 가정에 모순이다
따라서 $m$이 존재하는 최적구간은 없다□

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long ll;
 
int n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        vector<ll> v(n);
        for(int i = 0; i < n; i++) cin >> v[i];
 
        ll maxval = 0;
        loop(i, n-1) maxval = max(maxval, v[i]*v[i-1]);
        cout << maxval << endl;
    }
 
    return 0;
}cs