[JAVA] LeetCode 121 - Best Time to Buy and Sell Stock

 

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction

(i.e., buy one and sell one share of the stock),

design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

 

i일의 주식의 가격이 주어진 배열이 있다고 하자.

최대 한 번의 거래만 가능할 경우, 최대 이익을 얻기 위한 알고리즘을 작성하라.

단, 주식을 사기 전에는 주식을 팔 수 없다.

 

 

 

풀이 방법

1. 배열의 크기만큼 반복문을 수행하며 가장 주식이 저렴한 일자(인덱스)를 찾는다.

2. min_num엔 주식의 가격을, min_index는 해당 주식의 일자(인덱스)를 넣는다.

3. 현재 최소 가격을 가지는 주식의 인덱스보다 가격이 높은 경우를 찾는다.

4. 단, 현재 최소 가격이 가지는 일자(인덱스)보다 커야 한다.

5. 두 가격의 차이를 구하고, 이 차이가 최대가 되는 값을 구해 리턴한다.

 

 

class Solution {
    public int maxProfit(int[] prices) {
        int min_num = Integer.MAX_VALUE;
        int max_num = Integer.MIN_VALUE;
        int min_index = -1;
        int res = 0;
        
        for(int i=0; i<prices.length; i++) {
            if(prices[i] < min_num) {
                min_num = prices[i];
                min_index = i;
            }
            if((prices[i] > min_num) && (i > min_index)) {
                res = Math.max(res, prices[i] - min_num);
            }
        }
        return res;
    }
}