[leet] Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

Input 배열이 주어졌을 때 최대 이익을 구하는 문제입니다.

배열의 순서가 day라고 가정해서, 최대 이익의 발생값을 구하는 문제입니다.

public class Best_Time_to_Buy_and_Sell_Stock {
    public static void main(String[] args) {

        int[] prices = new int[]{7, 1, 5, 3, 6, 4};

        Best_Time_to_Buy_and_Sell_Stock b = new Best_Time_to_Buy_and_Sell_Stock();

        System.out.println(b.maxProfit(prices));
    }

    public int maxProfit(int[] prices) {

        int min_val = Integer.MAX_VALUE; // 값 초기화
        int max_profit = 0;

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

            if(prices[i] - min_val > max_profit) {
                max_profit = prices[i] - min_val;
            }
        }
        return max_profit;
    }

    // O(n^2)
    public int maxProfit2(int[] prices) {

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

        if (max > 0) {
            return max;
        } else {
            return 0;
        }
    }

}

배운 것 

최솟값을 초기화할 때 Integer.MAX_VALUE로 초기화를 한다.

Reference

https://www.youtube.com/watch?v=3RHCb8LY-X4 

https://www.youtube.com/watch?v=mANwJLY8BFo&t=1s