주식 11501 C++

이번 문제는 그리디로 풀면 되는 문제였습니다.
어떻게 풀지 몰라, 블로그를 참고하여서 풀었습니다.

처음 문제를 접했을때는, 정방향으로 배열을 순회하면서, Max값을 갱신해가면서 누적합을 구해야하나? 이런식으로 접근했는데
도저히 구현이 어려웠는데,

만약
1 1 3 1 1 5라면

앞에 1 1 에서 3에다가 팔아버리면 오답이다, 5에서 팔아야하기 때문이다.
이렇게 앞에서 부터 순회하면 어렵고

이걸 그냥 거꾸로 해서 5 1 1 3 1 1 해서 맨처음에걸 무조건 max로 두고,
그 다음 배열의 원소부터 max보다 작으면 anwer에다가 더하고, 만약 더 큰값이 나타나면 max값을 갱신하면 된다.

배열에 순방향으로 넣고 거꾸로 돌릴바에는, 그냥 deque로 앞에서 부터 넣는 방법을 선택하였다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <deque>

using namespace std;
int main() {
	int T = 0;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int a = 0;
		cin >> a;

		deque<long long>dq;
		for (int x = 0; x < a; x++) {
			int temp = 0;
			cin >> temp;

			dq.push_front(temp);
		}

		deque<long long>::iterator iter;
		int max = 0;
		long long answer = 0;
		for (iter = dq.begin(); iter != dq.end(); iter++) {
			if (iter == dq.begin()) {
				max = *iter;
			}
			else if (*iter < max) {
				answer += (max - *iter);
			}
			else {
				max = *iter;
			}
		}
		cout << answer << "\n";
	}
}