백만 장자 프로젝트

풀이

연속된 N일 동안 물건의 매매가를 알고 있고, 이를 이용해 미리 사고파는 작업을 하려 한다.
당국의 감시망에 걸리지 않기 위해 1만큼 구입하고, 판매는 구매 후 언제든 가능.

원재가 얻을 수 있는 최대이익을 구하도록 하자.

몇 가지 방법을 했었는데, 제한시간 초과로 통과하지 못했었다.
앞에서 하는 방법 때문에 문제가 있나 싶어서 뒤에서부터 검사하기로 했다.

1. 우선 반복문으로 모든 일자를 역순으로 돌았다.
2. 이 때 가장 큰 값을 찾아내며 돌았고, 만약 가장 큰 값인 max_value보다 이번 일자의 값이 더 작다면 그것을 이득으로 계산하기로 했다.
   이러니 시간 초과 없이 해결되었다.

T = int(input())
for testcase in range(1,T+1):
    earn = 0
    days = int(input())
    days_list = list(map(int, input().split()))

    max_value = 0
    for i in range(len(days_list)-1, -1, -1):
        if days_list[i] > max_value:
            max_value = days_list[i]
        else:
            earn += max_value - days_list[i]
    print(f'#{testcase} {earn}')

25년간의 수행 끝에 미래를 보는 능력으로 사재기라니..... 당황스럽다.