11501번: 주식

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


$O(tn)$

ai 뒤에서부터 차례대로 누적 최댓값을 maxi라 하자.
답은 sum(maxi-ai)

#include<cstdio>
int t, a[1000000];
int main() {
    for (scanf("%d", &t); t--;) {
        long long r = 0;
        int n, maxi = 0, i = 0;
        scanf("%d", &n);
        for (; i < n; i++) scanf("%d", a + i);
        while (i--) {
            if (maxi < a[i]) maxi = a[i];
            r += maxi - a[i];
        }
        printf("%lld\n", r);
    }
    return 0;
}