算法

(数学) $O(n)$

$\displaystyle ans_k = k * \max_{i = 1}^k \{A_i\} + kA_1 + (k - 1)A_2 + \cdots + A_k$

C++ 代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::max;
using ll = long long;

const int N = 2e5 + 10;

ll a[N], ans[N];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) cin >> a[i];

    ll mx = 0;
    for (int i = 1; i <= n; ++i) {
        mx = max(mx, a[i]);
        ans[i] = i * mx;
    }

    ll sum = 0, sum2 = 0;
    for (int i = 1; i <= n; ++i) {
        sum += a[i];
        sum2 += sum;
        ans[i] += sum2;
    }

    for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";

    return 0;
}