K - Sum - |Max - Min|

2 secs 1024 MB

まず、 $\mathrm{min}(B)$ と $\mathrm{max}(B)$ が定まっているとき、 $\mathrm{min}(B)$ 以上で $\mathrm{max}(B)$ 以下の要素は選んだ方が得であるということが分かります。なぜなら、負の項 $|\mathrm{max}(B)-\mathrm{min}(B)|$ に変化なくプラスの項 $\mathrm{sum}(B)$ を大きくできるからです。

$\mathrm{min}(B)$ を固定して考えます。( $\mathrm{max}(B)$ を固定しても結果は同じですが、今回は最小値を固定する方針で考えます。)

まず、配列 $A$ を昇順にします。
区間の左端のインデックス $i$ を小さいほうから見ていき、 $i$ 番目から何番目までの要素を選べばよいかを知りたいです。
仮に右端のインデックスを $j$ として、 $j$ と $j+1$ の差分を見てみます。
そうすると、右端をひとつ進めるごとに、 $\mathrm{max}(B)$ の値は大きくなりますが、 $\mathrm{sum}(B)$ の増加分がそれを上回るため、右端を進めた方が得であるとわかります。
よって、各 $i$ 番目から $N$ 番目を選んだ時のスコアのうち、最大値が答えとなります。

区間和を累積和を用いて求めることで全体の計算量は $\mathrm{O}(N)$ となります。

C++

xxxxxxxxxx
 
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
​
int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    vector<ll> sum(N + 1, 0);
    for (ll i = 0; i < N; i++) {
        sum[i + 1] = sum[i] + A[i];
    }
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ans = max(ans, (sum[N] - sum[i]) - abs(A[N - 1] - A[i]));
    }
    cout << ans << endl;
}

Python

xxxxxxxxxx
 
n = int(input())
A = list(map(int,input().split()))
​
A.sort()
CA = [0]
for i in range(n):
    CA.append(CA[-1] + A[i])
​
s = CA[-1]
ans = 0
​
for i in range(n):
    ans = max(ans, s - CA[i] -(A[-1] - A[i]))
​
print(ans)