Codeforces Round #735 (Div. 2)-A. Cherry

문제 설명

정수 $n$개 $a_1, a_2,..., a_n$ 이 주어졌을 때 $1 \le l < r \le n$ 를 만족하는 정수 쌍 $(l, r)$에 대해서 $max(a_l, a_{l + 1}, ..., a_r) \cdot min(a_l, a_{l + 1}, ..., a_r)$ 의 최대값을 출력하라.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10000)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 정수 $n (2 \le n \le 10^5)$ 가 주어진다.

각 테스트 케이스의 두번째 줄에는 $n$개의 정수 $a_1, a_2, ..., a_n (1 \le a_i \le 10^6)$ 가 주어진다.

Output
각 테스트케이스마다 주어진 수식의 최대값을 나타내는 정수를 출력한다.

Example
input
4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

output
12
6
4761
381274500335

문제 접근

사용한 알고리즘: 그리디 알고리즘
걸린 시간 : 00:02
생각보다 규칙을 빨리 발견해서 virtual에서는 빨리 풀었지만 규칙을 빨리 발견 못했으면.... codeforces 일주일동안 접었을 수도 있을 것 같았다. 생각보다 PS판에서 이런 비슷한 유형의 문제가 많다고 하니 지금 풀어본게 나중에 도움이 될것이라고 믿고 있다.

정해진 구간에서 최대값과 최소값의 곱을 구하고 이 값의 최대값을 구하는 문제이다. 여기서 우리가 생각할 것은 구간을 늘린다고 해서 최대값과 최소값이 무조건 바뀌는가? 이다.

예를 들어보자. 우리가 최대값을 찾아야 하는 배열은 다음과 같다. $[3, 2, 3, 1]$ 여기서 구간을 $(1, 2)$로 잡으나, $(1, 3)$ 으로 잡으나 구해야 하는 값은 같다. 또한 $(2, 4)$ 로 잡으나, $(3, 4)$로 잡으나 구해야 하는 값은 같다. 만약 다음과 같은 배열에서 $[1, 2, 3, 4]$, $(1, 2)$와 $(1, 3)$의 값을 구한다고 해서 $(1, 3)$ 이 답이 될수 있을까? 어짜피 $(2, 3)$ 을 구하면 이 답도 곧 아니라는 것을 알 수 있다.

즉 한 배열에서 우리가 확인해야할 구간은 크기가 2인 구간뿐 밖에 없으며 나머지는 절대로 답이 될 수가 없다. 왜냐하면 크기가 2가 넘어가면 어떠한 방식으로든 크기가 2인 구간의 답으로 구할 수 있기 때문이다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        long long arr[n], ans = -1;
        for(int i = 0; i < n; i++) cin >> arr[i];
        for(int i = 0; i < n - 1; i++) ans = max(ans, arr[i] * arr[i + 1]);
        cout << ans << "\n";
    }
    return 0;
}