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

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150 

Best Time to Buy and Sell Stock - LeetCode

문제 유형 : 배열

문제 난이도 : Easy

 

문제

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

prices[i]는 i번째 날의 주식 가격입니다.

기간동안 얻을 수 있는 최고의 수익을 구하시오. 수익을 구할 수 없으면, 0을 반환하시오

 

풀이

prices를 0번부터 n-1번까지 탐색하면서,

가장 작은 값을 구한다.

가장 작은 값을 구하고, 이전까지 가장 큰 수익과 이번 수익(지금의 가격 - 가장 싼 값) 중 더 큰 값을 계속 갱신시킨다.

 

코드(C++)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        int maxProfit = 0;
        int minPrice = prices[0];

        for (int i = 1; i < n; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                maxProfit = max(maxProfit, prices[i] - minPrice);
            }
        }

        return maxProfit;
    }
};