C++ 121. Best Time to Buy and Sell Stock(Leet Code)

Leet Code_121. Best Time to Buy and Sell Stock

Dynamic Programming

 

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

싸게 사서 비싸게 판 마진의 최대값

​

방법

1. 파는 값은 사는 값보다 비싸야한다.

 

결과

싸게 사서 비싸게 판 마진의 최대값

 

통과한 코드

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = 0;
        for (int i = 0; i < prices.size(); i++)
        {
            int buy = prices[i];

            for (int j = i + 1; j <= prices.size() - 1; j++)
            {
                int sell = prices[j];
                if (buy < sell && n < (sell - buy))
                    n = sell - buy;
            }

        }
        return n; 
    }
};

속도 1480ms

 

다른 사람 코드

class Solution {
public:
    int maxProfit( vector<int>& prices ) {
        int minPrice = INT_MAX, maxProfit = 0;
        for( int i=0; i < prices.size(); i++ ) {
            maxProfit = max( maxProfit, prices[i] - minPrice );
            minPrice = min( minPrice, prices[i] );
        }
        return maxProfit;
    }
};

속도 8ms

어마어마한 속도 차이..

for문을 한번만 돌며 바로 값을 구했다

DP로 푼다고 풀고나서 다른 사람 코드 보는데 이해하기가 어렵다. 몇 분동안 들여다 보고나서 이해한 코드