문제

[백준] 최대상승

접근

1. 가장 큰 것을 뒤에서부터 찾는다
2. 찾는 동시에 현재 데이터를 빼본다
3. 그 중에 최대값을 가지는 것을 찾는다

작은 것은 앞, 큰 것은 뒤 순서가 중요하다

이 문제를 풀기 위해서 반대로 접근도 가능하다

1. 가장 작은 것을 앞에서부터 찾는다
2. 찾는 동시에 현대 데이터를 뺀다
3. 그 중에 최대값을 찾는다

이렇게 하면 최소값은 발견한 것 가장 작은 것으로 갱신한다
이것은 그 당시에 가장 작은 것이다

최고가격은 업데이트 하는 순간에만 존재할 수 밖에 없다

두번의 max 비교

1. 발견한 가격 중 가장 작거나 큰 것
2. 그 순간의 차이

두번의 max 비교가 중첩되어 있는 게 이 문제를 헷갈리게 하는 부분이다
하지만 다음에 유용하게 쓰일 수 있을 것 같다

자주발견되는 문제 유형

이런 문제 유형을 여러 문제에서 본 적이 있다
이걸 보면 스타크래프트의 맵이 생각난다

탐험을 하면 보이는 곳이 많아진다
하지만 지금의 최선은 발견한 것 중에 있다

발견하면서 계속 최고를 갱신해간다
이런 문제해결 방식의 특징은 현재 밝혀진 모든 데이터를 다시 탐색하지 않는다는 데 있다

다시 탐색하지 않는다 -> 최고를 갱신한다

해결

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


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

	vector<int> v;

	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	int maxv = -1;
	int ans = 0;
	for (int i = v.size()-1; i >= 0; i--) // 이 문제는 두번의 max 비교가 있다
	{
		if (v[i] > maxv) {				  // 1. 첫번째 발견한 것 중 최고가격
			maxv = v[i];
		}
		ans = max(ans, maxv - v[i]);	  // 2. 발견했을 때 판매한 최고 가격
	}
	cout << ans;
}

// 뒤에서부터 max 찾고 현재값 뺌
// 그 중 젤 큰 게 답


// ref : https://dkswnkk.tistory.com/664

개념정리

개념
중첩된 max	max를 중첩하여 다양한 문제를 풀 수 있다