Maximum Cake Tastiness-Codeforces

問題リンク-Maximum Cake Tastiness

問題

$n$個のケーキがあり$i$番目のケーキの重さは$a_i$です。
ケーキのおいしさはは隣り合う2つのケーキの重さの最大値です。つまり、$\max(a_1+a_2, a_2 + a_3, ... , a_{n-1} + a_{n})$です。
以下の操作を最大で1回行うことができます。

$a$の部分列$[l,r](1 \leqq l \leqq r \leqq n)$を選び反転させる。

操作後、ケーキのおいしさは最大でいくつになるかを出力してください。

解法

2つの最大値の合計が答えです。

それぞれを$a_i, a_j$とします。$(i < j)$の時、$[i, j-1]$と選ぶことによって2つの最大値が隣り合います。

実装

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0;i < n; ++i){
        cin >> a[i];
    }

    sort(a.rbegin(), a.rend());

    cout << (a[0] + a[1]) << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}