[Easy] 121. Best Time to Buy and Sell Stock

각 [i] day의 주식 가격이 담긴 int형 배열이 주어지고, 주식을 사고 팔아야 할 때 수익을 최대화하면 수익이 얼마인지 구하는 문제이다. 예를 들어 첫 번째 예에서 가격이 1일 때 사서 6일 때 팔면 수익이 5로 최대가 된다.

처음엔 배열 profit을 선언하고 profit[i]를 i에서 살 때 최대 수익으로 정의했었다. 그러면 price[i]를 기준으로 그 뒤에 가격들에 대하여 한 번씩 확인하였다. 즉 이중 루프가 되는데 시간 초과가 떴다.

아직 알고리즘 문제를 많이 접해보지 않아서 그런지 방법이 바로 생각나지 않았다. 생각을 좀 해보다가 profit[i]를 i에서 살 때가 아닌 팔 때의 최대 수익으로 정의하였더니 쉽게 풀렸다. 우선 profit[0]은 항상 0이 된다. 그리고 i 이전의 min 값을 따로 기억해둔다. 그리고 현재 가격과 이전의 최솟값을 비교하면서 최대가 되는 profit을 구하면 된다.

int maxProfit(vector<int>& prices) {

	// profit[i]: prices[i]에서 팔 때 최대 수익
	vector<int> profit(prices.size());
	profit[0] = 0;

	int curMin = prices[0];
	for(int i = 1; i < prices.size(); ++i)
	{
		if(curMin < prices[i])
			profit[i] = prices[i] - curMin;
		else
			profit[i] = 0;

		curMin = min(curMin, prices[i]);
	}

	return *max_element(profit.begin(), profit.end());
}