LeetCode 121. Best Time to Buy and Sell Stock

121.Best Time to Buy and Sell Stock

문제

주어진 배열 prices는 prices[i]가 i번째 날의 특장 주식 가격을 나타냅니다.

당신은 한 주식을 사는 날과 미래의 어느 다른 날에 그 주식을 판매하여 이윤을 극대화하려고 합니다.

이 거래로부터 얻을 수 있는 최대 이익을 반환하세요. 만약 어떤 이익도 얻을 수 없다면 0을 반환하세요

의사코드 또는 풀이 계획

1. 시간 초과

1. prices에 i포인터가 가리키게 한다.
2. i 포인터가 가리키는 값과 또 다른 j 포인터가 가리키는 값을 비교한다.
3. 두 값의 차이가 가장 큰 값을 반환한다.

2. 최소값을 찾고 그 이후의 값만 비교한다.

1번 방법은 prices 배열의 거의 모든 값들을 서로 비교한다. 
그럼 이 비교를 줄일 수 있는 방법이 뭐가 있을까?
최소값을 찾고 그 이후의 값들과 찾은 최소값만 비교하면 되지 않을까?
라고 생각했지만 해당 풀이로는 아래의 케이스를 커버할 수 없다
prices = [2, 4, 1]
최소값은 1이다. 그래서 나의 풀이로는 prices[2] 이후에 값이 없기 때문에 0을 리턴하게 되는데, 
해당 케이스의 경우 2에서 사서 4에서 팔면 2의 이득이 발생한다.

풀이 (해결 못함)

1. 시간 초과

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;

        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if(prices[j] - prices[i] > maxProfit) {
                    maxProfit = prices[j] - prices[i];                    
                }
            }
        }

        return maxProfit;
    }
}

2. 두 번째 시도 - 틀림

class Solution {
    public int maxProfit(int[] prices) {
        int minimum = 100000;
        int minimumIndex = 0;

        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minimum) {
                minimum = prices[i];
                minimumIndex = i;
            }
        }

        if (minimumIndex == prices.length - 1) {
            return 0;
        }

        int maxProfit = 0;
        for (int i = minimumIndex; i < prices.length; i++) {
            if (prices[i] - minimum > maxProfit) {
                maxProfit = prices[i] - minimum;
            }
        }

        return maxProfit;
    }
}

다른 풀이

int 구매 금액 중 가장 낮은 값 = Integer.MAX_VALUE
int 최대 이익 = 0;
int 오늘 주식을 팔았을 경우에 발생하는 이익 = 0;

for (int i = 0; i < prices.length; i++) {
	if (prices[i] - lsf) // 현재의 가격이 이전의 구매 가격보다 낮다면
    	구매 금액 중 가장 낮은 값 = prices[i];
    
    오늘 주식을 팔았을 경우에 발생하는 이익 = 현재 주식 가격 - 구매 금액 중 가장 낮은 값;
    
    if (최대 이익 < 오늘 주식을 팔았을 경우에 발생하는 이익)
    	최대 이익 = 오늘 주식을 팔았을 경우에 발생하는 이익
}

return 최대 이익;

class Solution {
    public int maxProfit(int[] prices) {
        int lsf = Integer.MAX_VALUE;
        int op = 0;
        int pist = 0;
        
        for(int i = 0; i < prices.length; i++){
            if(prices[i] < lsf){
                lsf = prices[i];
            }
            pist = prices[i] - lsf;
            if(op < pist){
                op = pist;
            }
        }
        return op;
    }
}