[C++] Leetcode: Best Time to 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

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.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

 

일단 우선 딱 보고 생각나는 거는 브루트 포스긴 하다.

2중 for문으로 돌면서 전부 체크해서 정답을 내면 된다.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int answer = 0,sellIndex,buyIndex;
        for(buyIndex = 0; buyIndex < prices.size() - 1;buyIndex++){
        	for(sellIndex = buyIndex + 1; sellIndex < prices.size(); sellIndex++){
            	answer = max(answer, prices[sellIndex] - prices[buyIndex]);
                }
            }
        return answer;
    }
};

 

그래도 시간 복잡도가 O(n^2)이다보니까 

시간 제한에서 걸려버린다.

 

줄일려면 투포인터를 사용해서 줄일수가 있었다.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int answer = 0,sellIndex = 1,buyIndex = 0;
        while(sellIndex != prices.size()){
            answer = answer > prices[sellIndex] -prices[buyIndex] ? answer : prices[sellIndex] - prices[buyIndex];
            if(prices[sellIndex] < prices[buyIndex]) buyIndex = sellIndex;
            sellIndex++;
        }
        return answer;
    }
};

buyIndex랑 sellIndex에서 sellIndex를 순회시키면서 prices[sellIndex]가 prices[buyIndex]보다 싸다면 옮겨서 새로 기회를 보는 거다. buy price를 최소화시키면 다음 index에 더 큰 이익이 나올수가 있으니깐.