LeetCode[day5] - Best Time to Buy and Sell Stock II

 

Say you have an array prices for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

 

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.   Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

 

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.   Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are   engaging multiple transactions at the same time. You must sell before buying again.

 

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

1. 알고리즘을 해결하기 위해서 생각한 방법 (주의 깊게 읽지 말 것)

 

 - [7,1,5,3,6,4] Input이 주어졌을 때, 알고리즘 로직은 판매, 구매, 아무것도 안 한다. 라는 조건이 있을 것이라고 생각

 - 판매 했을 때는 다음에는 어쩔 수 없이 구매해야한다. 라고 생각

 - 그렇게 되면, 이번에 주식을 구매해서 다다음에 파는 것과 이번에 주식을 구매해서 다음에 파는 것,

 이번엔 쉬고, 다음에 주식을 구매해서 다다음에 파는 것과 다음에 주식을 구매해서 다음에 파는 것이 있을 것이라고 생각을 했다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 어려운 점은 구매, 판매, 아무것도 안 한다가 있을 것 같았다.

 - 그리고, 주식을 거래하면 그 다음에 영향을 줄 것이라고 생각을 했다.

 - 일반화된 로직을 찾기 어려웠다.

 - 결국 못 풀었다.

 - 어려운 문제인가 싶었다.

 

3. 내가 작성한 알고리즘

 

class Solution {
    //어려운 점 1 : 조건이 판매한다. 구매한다. 아무것도 안 한다. 세 가지로 나뉘어 진다.
    //해당 상태는 다음 상태에 영향을 줄 것이라고 생각한다. 그러면 계속해서 값을 새롭게 구해야하는게 아닐까?
    //[7,1,5,3,6,4] => [-6,4,2,3,-2]
    //[-6, 4, -2, 3, -2]
    //[1,2,3,4,5] => [1,1,1,1,1]
    public int maxProfit(int[] prices) {
        int profit = 0;
        //Math.max(prices[i+2] - prices[i], prices[i+1] - prices[i]) => -2
        //Math.max(3 - 1, 5-1) => 4
        //Math.max(1, -2) => 1
        //Math.max(1, 3) => 3
        //benefit += Math.max(benefit+Max, benefit+Max+1)-> 7
        //조건 : 판매한다. 구매한다. 아무것도 안 한다.
        //어려운 점 2: 다음에 나오는 이익, 그 다음의 다음 날 나오는 이익을 위해서는 prices.length에서
        //3의 길이를 빼줘야 한다. 여기에서 일반화 되지 않은 코드가 추가 됨.
        //예를 들면 length == 2인 케이스
        for(int i=0; i<prices.length-3; i++){
            int mayBeNextProfit = Math.max(prices[i+2] - prices[i], prices[i+1] - prices[i]);
            int mayBeNextNextProfit = Math.max(prices[i+3] - prices[i+1], prices[i+2] - prices[i+1]);
            if(mayBeNextNextProfit > mayBeNextProfit){
                i++;
            }
            profit += Math.max(0, Math.max(mayBeNextProfit, mayBeNextNextProfit));
        }
        
        if(prices.length == 2){
            profit = Math.max(0, prices[1] - prices[0]);
        }
        return profit;
    }
}

 

4. 다른 사람이 작성한 알고리즘 보기

 

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        //[7,1,5,3,6,4]
        //[1,2,3,4,5]
        //[7,6,4,3,1]
        for(int i=1; i<prices.length; i++){
            int diff = prices[i]-prices[i-1];
            if(diff > 0){
                profit += diff;
            }
        }
        return profit;
    }

 

5. 다른 사람이 작성한 알고리즘을 보고 배운점

 아... 쥰내 똑똑하다.

 다음에 주식을 구매한 가격에서 이전 주식을 구매한 가격 = 이익

 [1,2,3,4,5]에 대입을 한다면, 

 2.minus(1) -> 1, 3.minus(2) -> 1, 4.minus(3) -> 1, 5.minus(4) ->1, 4의 이익이 나온다.

 - 그러면 한 번의 이익이 나오면 거래한 것인가?

이익만 나오고, 결과를 팔지 않았기 때문에 간만 본 것이다.

- 판매할 때는 언제인가?

 실제로 diff가 0이거나, 최종 결과 값에 도달하면 자동으로 판매되는 로직이다.

- 타이밍에 맞게 큰 값이 나오거나 그럴 때 구매해야하는 것이 아닌가?

 앞 값과 전 값의 차인, 이익의 관점에서 보기 때문에 이익의 합은 연속적인 이익 구간이기 때문에 고려할 필요가 없었다.

 

6. 짝짝짝 결과

 

나에게 반성을 하라고 엿을 주셨다.

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3287/

Explore - LeetCode