122. Best Time to Buy and Sell Stock II - C

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).

Example 1:

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.

Example 2:

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.

Example 3:

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

Answer 1: Wrong Answer

int maxProfit(int* prices, int pricesSize){
    int max = prices[0], min = prices[0];
    int maxid = 0, minid = 0;
    int state = 0;
    int p = 0;
    int sum = 0, sum2 = 0;
    int i, j;
    
    // 최대 최소 구하기
    for(i=0;i<pricesSize;i++)
    {
        if(max < prices[i])
        {
            max = prices[i];
            maxid = i;
        }
        
        if(min > prices[i])
        {
            min = prices[i];
            minid = i;
        }
    }
    
    for(i=0;i<pricesSize;i++)
    {
        // Buy
        if(state == 0 && prices[i] < max && i != pricesSize-1)
        {
            p = prices[i];
            state = 1;
        }
        
        // Sell
        if(state == 1 && p < prices[i])
        {
            sum += prices[i] - p;
            state = 0;
        }
        
        // 마지막 idx에 sell 못했을 경우
        if(state == 1 && i == pricesSize-1)
        {
            
        }
    }
    
    // 최소가 최대보다 앞에 있으면 최대 최소간의 Buy -> Sell 구하기
    if(minid < maxid)
    {
        sum2 = max-min;
    }
    
    printf("max: %d min: %d\n", max, min);
    printf("sum: %d sum2: %d", sum, sum2);
    
    if(sum2 > sum)
    {
        sum = sum2;
    }
    
    return sum;
}

Buy, Sell의 조건식이 완전하지 않음..

다시 생각해볼 CASE: [6,1,3,2,4,7]
Buy(1) Sell(3) = 2, Buy(2) Sell(7) = 5
=> 7

처음 생각한 접근 방식

• 무조건 Buy -> Sell 순서여야 한다.
• Buy 한 건 팔아야 한다.

1) max, min 이용
max idx > min idx 일 경우, profit: max - min
== 일 경우, 0
< 일 경우, X...
이걸 사전 조건으로..?

i == max idx 일 경우, Buy X

2) 현재 상태를 나타내는 state 변수
0: Buy 전
1: Buy 후, Sell 전
2: Sell 후(, Buy 전)

or 0: Buy 대기, 1: Sell 대기

이걸 이용해서
state == 0 && i == min idx && i != pricesSize => Buy
state == 1 && i == max idx => Sell

3) 이중 for문...? [X]
prices[i] < prices[j] => Buy
prices[i] > prices[j] => Sell

4) 마지막으로 Buy 한 금액을 담는 변수 p
Buy 할 때, p = prices[i];
p < prices[i] => Sell

Sell 할 때, sum += prices[i] - p;

5) 가까운 시일 내에 파는 것과 max-min의 경우를 비교해서 profit 계산

Answer 2: Accepted

int maxProfit(int* prices, int pricesSize){
    int sum = 0;
    int i;
    
    for(i=0;i<pricesSize-1;i++)
    {
        // Sell
        if(prices[i+1] > prices[i])
        {
            sum += prices[i+1] - prices[i];
        }
    }
    
    return sum;
}

..몇십줄이던 내 코드가 부끄러워지는 순간

Sell 한 시점에 Buy 도 할 수 있다는 것을 생각하지 못함
그래도 이건 너무 간단한 거 아닌지..;