백준 s2 11501 주식 c++

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

11501번: 주식

 

풀이

 

가장 최대로 수익을 얻으려면, 항상 고점에서 팔아야 한다.

max값이 나올 때까지 주식을 하나씩 사다가, max값이 나오면 그때 다 판다.

또, 남은 주식들 중 max값이 나올 때까지 주식을 하나씩 사다가 max값이 나오면 그때 다 판다.

 

처음에는 앞에서부터 팔려고 했으나, 남은 기간 중 max값을 구하기 어려워 뒤에서부터 시작했다.

 

만약 max값보다 가격이 낮다면, 그 주식을 mx값에 팔면 되고, 새로운 max값을 만나면 max값을 업데이트 하면 된다.

 

전체 코드

 

/*boj s2 11501 주식*/
#include <algorithm>
#include <iostream>
#define MAXN 10000005
using namespace std;

int T, N;
long long arr[MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
        long long ans = 0;

        int mx = arr[N - 1];
        for (int i = N - 1; i >= 0; i--) { // 뒤에서부터 접근,
            if (mx < arr[i]) {             // 내가 갖고 오던 max값보다 크면 바꾸기
                mx = arr[i];
            } else { // 내가 갖고 있는 max값에 주식 팔기
                ans += (mx - arr[i]);
            }
        }

        cout << ans << "\n";
    }
}