https://www.acmicpc.net/problem/1744

✍️ 첫번째 접근

모든 수를 입력받아 오름차순으로 정렬하고, 그 배열에서 작은 수부터 큰 수까지와 큰 수부터 작은 수까지 각각 계산을 한 후 둘 중 최대값을 답으로 한다. 이때 이 계산은 어떤 수와 어떤 수를 묶거나 혹은 묶지 않고 최대값을 얻을 수 있어야 한다. 또한 한번 묶인 수는 더 이상 묶일 수 없다는 조건을 만족해야 한다.
하지만, 이렇게 하였을 때 다음과 같은 반례가 있어서 이러한 방식으로는 해결할 수 없다.

6
-8
-7
-6
6
7
8

#include <bits/stdc++.h>
using namespace std;
long long arr[60];
long long n;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(long long i = 0; i < n; i++)
        cin >> arr[i];

    if(n == 1) {
        cout << arr[0];
        return 0;
    }
    sort(arr,arr+n);

    long long sum_up = 0;
    for(long long i = n-1; i >= 1; i--) {
        if((arr[i] == 0) && (arr[i-1] < 0) && (i >= 2)) {
            sum_up += arr[i];
        }
        else if(arr[i] * arr[i-1] > arr[i] + arr[i-1]) {
            sum_up += arr[i] * arr[i-1];
            --i;
            if(i == 1) {
                sum_up += arr[i-1];
                break;
            }
        }
        else {
            sum_up += arr[i];
            if(i == 1) {
                sum_up += arr[i-1];
                break;
            }
        }
    }

    long long sum_down = 0;
    for(long long i = 0; i <= n-2; i++) {
        if(arr[i] * arr[i+1] > arr[i] + arr[i+1]) {
            sum_down += arr[i] * arr[i+1];
            ++i;
            if(i == n-2) {
                sum_down += arr[i+1];
                break;
            }
        }
        else {
            sum_down += arr[i];
            if(i == n-2) {
                sum_down += arr[i+1];
                break;
            }
        }
    }

    cout << max(sum_up, sum_down);

    return 0;
}

✍️ 두번째 접근

약간의 힌트를 얻어, 모든 수를 한꺼번에 정렬하여 계산을 하지 말고 양수와 음수를 나누어 계산을 실행하였다. 만약 수가 1일 경우에는 다음과 같은 경우에서 3이 아니라 5가 나와야 하므로 따로 계산해주었다.

5
1
1
1
1
1

#include <bits/stdc++.h>
using namespace std;
long long ans;
void seqNum(vector<int> v) {
    while(v.size() > 1) {
        ans += *(v.end() - 1) * *(v.end() - 2);
        v.pop_back();
        v.pop_back();
    }
    if(v.size() == 1)
        ans += v[0];
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<int> seqP, seqN;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if(num == 1)
            ++ans;
        else if(num > 0) {
            seqP.push_back(num);
        }
        else {
            seqN.push_back(num);
        }
    }
    sort(seqP.begin(),seqP.end());
    sort(seqN.begin(),seqN.end(),greater<>());
    seqNum(seqP);
    seqNum(seqN);
    cout << ans;

    return 0;
}