배열 최대/최소 기억

#include<iostream>
#include<vector>
using namespace std;
int mem[100001];
int solution(vector<int> prices)
{
	int min = 1000001;
	for (int i = 0; i < prices.size(); i++) {
		if (prices[i] < min) {
			min = prices[i];
		}
		mem[i] = min;
	}
	int max = 0;
	for (int i = 0; i < prices.size(); i++) {
		if (prices[i] - mem[i] > max) {
			max = prices[i] - mem[i];
		}
	}
	return max;
}

 

prices 배열의 어떤 index까지의 최솟값을 mem 배열에 저장한다.

 

가령 prices = {1,5,2,6,2,4,0} 이런 상황이라면 mem = {1,1,1,1,1,1,0} 이렇게 되는 것이다.

 

최소의 가격일 때 구매해서 최대의 가격에 되팔아서 이윤의 최대치를 구하는 문제에 이용할 수 있다.

 

index가 시간을 의미한다고 볼 수 있다. 같은 index에서 prices와 mem의 차이가 가장 큰 지점이 정답이 된다.

 

최대 마진을 내야 하는 경우로 기억