[BOJ 2036] 수열의 점수

어떻게 하면 수열의 점수를 최대화 할 수 있는지 생각해보자. 

1. 음수는 더하는 것보다 음수와 곱해서 양수로 만들거나 0과 곱해 제거하는 것이 이득이다. (음수에서 양수 혹은 0이 되어 점수가 커진다)

2. 양수는 곱하면 이득이다. 단, 1은 곱하는 것보다 더하는 것이 이득이다. 

3. 두 수를 곱할 때는 절댓값이 큰 수부터 곱하는 것이 이득이다. (2, 3, 4에서는 3, 4를 먼저 곱하는 것이 이득)

 

이렇게 크게 3가지 경우가 있다. 이를 조건 분기를 잘 진행해주면 해결 가능하다. (곱해지는 수가 크다. 자료형을 유의하자.)

int main(void) {
    fastio;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> A[i];
    sort(A, A + n);

    ll score = 0;
    int s = 0;
    for (int i = 0; i < n; i++) {
        if (A[i] > 1) break;
        else if (i == n - 1) score += A[i];
        else if (A[i] < 0 && A[i + 1] < 0) score += A[i] * A[i + 1], i++;
        else if (A[i] < 0 && A[i + 1] == 0) i++;
        else score += A[i];
        s = i;
    }
    for (int i = n - 1; i > s; i--) {
        if (i == s + 1) score += A[i];
        else score += A[i] * A[i - 1], i--;
    }
    cout << score;
    return 0;
}