[알고리즘] Leetcode_121_Best_Time_to_Buy_and_Sell_Stock

Problem

Solve

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        int max = Integer.MIN_VALUE;

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

        return result > max ? result: max;
   }
}

for 문 두 번 돌면서 현재 사서 다음 팔 떄 수익을 max 로 두고 반환한다.
201번째인가 부터 time limit 이 떴고 O(n^2)가 되지 않는 방법을 찾아본다.

class Solution {
    public int maxProfit(int[] prices) {
    	int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for(int price : prices){

            min = Math.min(price,min);//살 시점 => 가장 작은 값
            max = Math.max(price - min, max); //현재 -min + price =  수익 => 가장 큰 값
            System.out.println(min +" "+ max);
        }
        return max;
    
    }
 }

수익이 가장 많이 남으려면 최저점에서 사고 최고점에서 팔아야한다.
이때 min과 max 를 활용하는데, 말 그대로
알고자하는 최저값은 가장 낮은 주식 가격이다. min = Math.min(min, price)
알고자하는 최고값은 수익이다. max = Math.max(max, price-min)

이를 토대로 반환하고자 하는 것은 수익이므로 max를 리턴한다.