[알고리즘/백준] 11501번 : 주식(python)

처음에는 앞에서 부터 비교한다고 생각했다.

T = int(input())
for _ in range(T):
    N = int(input())
    a = list(map(int, input().split()))
    result = []
    r = 0
    for idx, k in enumerate(a):
        if idx == (len(a)-1):
            r += (k*len(result)) - (sum(result))
            result = []
        elif k >= a[idx + 1]:
            result.append(k)
        else:
            r += (k*len(result)) - (sum(result))
    print(r)

이렇게 하면 답이 안나온다... 시간초과도 나고...

그래서 생각을 바꿔서 뒤에서 부터 제일 큰 수를 가지고 하나씩 빼서 결과에 더하자고 생각했다.

T = int(input())
for _ in range(T):
    N = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    result = 0
    tmp = 0
    for i in a:
        if tmp > i:
            result += (tmp - i)
        elif tmp < i:
            tmp = i
    print(result)