Array - Best Time to Buy and Sell Stock II

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/564/

Explore - LeetCode

 

Note : 

• 한번에 두개를 동시에 살 수 없다. 

 

Solution : 

•   결국 비쌀때 샀다, 쌀때 팔면 되는 것인데, 구간별 누적합이, 전체 최대차의 합과도 결국 같다는 아이디어가 떠올라야 최적화가 가능한 문제.

 

Retro :

•  생각해 내느냐, 찾아내느냐 그것이 문제다. 하지만 기본적으로 알아야, 찾아내는 단계에서 그걸 바탕으로 다시 생각해내는 단계로 진입할 수 있다. 
•  Brute Force를 우선 제일 먼저 해 보자. 이것이 인간이 우선 인식하는 방식이다. 이후에 컴퓨터를 위해 다른 최적화를 시도 해 보자.
• 양극의 예외처리를 정규 로직에 더 쉽게 넣는 방법은 없을까.. 

  

내 해는 쌀때를 찾고 비쌀때를 찾아서 그 합을 더하는 로직. 더 최적화의 여지는 충분.

public class Solution {
    public int MaxProfit(int[] prices) {
        if(null==prices || prices.Length<=1)
            return 0;
        int profit  = 0;
        int idxBuy  = -1;
        for(int k = 0; k < prices.Length-1; ++k)
        {
            if(prices[k+1] > prices[k])
            {
                if(idxBuy==-1) 
                    idxBuy  = k;
            }
            else if(prices[k+1] < prices[k])
            {
                if(idxBuy >= 0)
                {
                    profit += (prices[k] - prices[idxBuy]);
                    idxBuy  = -1;
                }
            }
            if(idxBuy>=0 && prices[k+1]>prices[idxBuy] && k+2==prices.Length)
            {
                profit += (prices[k+1] - prices[idxBuy]);
                break;
            }
        }
        return profit;
    }
}