[LeetCode/easy/Array] Best Time to Buy and Sell Stock

 

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

Best Time to Buy and Sell Stock - LeetCode

 

배열을 쭉 훑는 for문을 지나면서 minn을 구하는데 만약 minn보다 작은 게 나오면 해당 원소 다음의 sub array 내에서 max 값을 찾는다.

그 후, minn을 업데이트하고 answer 에 더 큰 값을 넣어준다 (sell-minn와 이전 answer 값 사이의)

 

int maxProfit(vector<int> prices) {
    int sell=0;
    int answer = 0;
    int minn = 10001;
    
    for(int i=0; i<prices.size(); i++){
        if(minn > prices[i]){
            sell = *max_element(prices.begin()+i, prices.end());
            minn = prices[i];
            answer = max(answer, sell-minn);
        }
    }
    return answer;
}

 

 

[다른 사람 코드]

깔끔하고 다시 보면 좋을거 같아서 가져왔다.

여기 보면 어차피 왼쪽에서 오른쪽으로 이동하면서 원소를 체크하기 때문에 구현할 수 있는 방법이다.

mini가 업데이트될 수도 있고, 안될 수도 있다. 이 때문에 그냥 mini 업데이트와 res 업데이트를 동시에 할 수 있다.

 

7, 3, 5, 6, 2, 8의 경우

mini = 3, prices[2] = 5 일 때는 mini는 업데이트되지 않고 res = 2

mini = 3, prices[3] = 6 일 때는 mini는 업데이트되지 않고 res = 3

prices [4] = 2일 때 mini가 2로 업데이트되고 res = 3으로 그래도 유지

mini = 2, prices[5] = 8 일 때는 mini는 업데이트되지 않고 res = 6 업데이트

 

int maxProfit(vector<int>& prices) {
    int mini = INT_MAX;
    int res = INT_MIN, n=prices.size();
    for(int i=0;i<n;i++) {
        mini = min(mini, prices[i]);
        res = max(res, prices[i] - mini);
    }
    return res;
}

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/discuss/2429508/Simple-solution-in-CPP-O(N)