[leetcode] 122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II

문제

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

i번째 원소가 i일의 주식 가격을 의미하는 prices라는 array가 존재한다. 

최대 이익을 얻을 수 있도록 알고리즘을 설계해라. 원하는 만큼 거래를 완료할 수 있다.

(예: 주식 1개 구매 후 1개 파는 행위 반복 가능 → i일에 팔고, i일에 다시 구매 가능)

 

Note: 동시에 여러 거래를 할 수 없다.

(즉, 주식을 새로 구매하기 전에 기존 주식을 팔아야 함)

풀이

처음 이 문제에 접근할 때에 어떻게 하면 이익을 최대로 할 수 있을까 고민을 했다. 그래서, 큰 배열을 만들어서 거기에 각각의 경우를 다 저장하고 그 중 제일 큰 값을 찾아야 하는 줄 알았다.

생각해보니, prices = [1,2,3,4]라고 아래와 같은 결과를 보여준다는 것을 알 수 있었다.

# case 1
(pricse[1] - prices[0]) + (prices[2] - prices[1]) + (prices[3] - prices[2]) = 3

# case 2
(prices[3] - prices[0]) = 3

▶ 그냥 i번째와 (i-1)번째를 비교해서 i번째가 (i-1)번째보다 크면 계속 사고 팔면 최대 결과가 나온다는 것이다.

답안

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxprofit = 0;
        for(int i = 1; i < prices.size(); i++) {
            if(prices[i] > prices[i-1])
                maxprofit += (prices[i] - prices[i-1]);
        }   
        return maxprofit;
    }
};