[백준 11501 c++] 주식

 

i-1에서 최대값이 존재했다면, 현재 i 노드부터 마지막 노드 까지의 최대값을 매번 갱신해야하는 문제이다.

 

그대로 구현할 경우에는 시간복잡도가 n*m*v가 되므로, 다른 방식을 사용해야한다.

 

매번 최대값을 찾는 것이 아니라, 매 테스트 케이스 시작에서 각 배열에 맞는 최대값을 미리 구해놓는다.

 

노드의 시작점부터 구하는 것이 아니라, 마지막 노드부터 내려가면서 구해야한다.

 

#include <iostream>
#include <algorithm>

int list[1000001] = {};
int listMax[1000001] = {};

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n;
	std::cin >> n;

	while (n--) {
		int m;
		std::cin >> m;

		int k = 0;
		for (int i{ 0 }; i < m; i++) {
			std::cin >> list[i];
			k = std::max(k, list[i]);
		}

		int q = 0;
		for (int i{ m - 1 }; i >= 0; i--) {
			if (q < list[i]) q = list[i];
			listMax[i] = q;
		}

		long long ans = 0;
		for (int i{ 0 }; i < m; i++) {
			ans += listMax[i] - list[i];
		}

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