[Leetcode] 121. Best Time to Buy and Sell Stock]

Identifying the Problem

주식 price 수열 내에서 가장 큰 수익을 구한다.

price의 index는 증가는 시간 증가이다.

가장 쌀 때 사서 가장 비쌀 때 팔았을 때 이익을 구하는 문제이다.

Organizing thoughts

즉 profit은 0보다 커야하고, profit는 sell-buy 가 max 인 값이다.
그리고 마지막날에 산건 의미가 없다.

핵심 idea 는 한 arr을 탐색하는 인덱스를 선발과 후발로 나누면 한 arr가 2개로 복사되는 효과를 본다.
선발로 price[i]을 설정해 일반적으로 탐색하고,

후발은 min으로 가장 쌀 때의 가격을 저장해둔다.

따라서 price[i] 와 min의 차이를 profit으로 정하고, profit이 max인 경우를 리턴하면 된다.

Sourcecode

int maxProfit(int* prices, int pricesSize)
{
    
    int i = 0;
    int profit =0;
    int max=0;
    int min=prices[i];  
    
    
    
    for(i=1; i<pricesSize; i++)
    {   
        if(min > prices[i]) 
        	min = prices[i];
        
        else
        {
      		profit = prices[i]-min;
       		if(profit > max) max = profit;
        }
        
    }
        
    return max;
}