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

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

---

문제

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

 

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

---

풀이

풀이 과정

하루마다의 주식 가격이 담겨 있는 prices 배열이 주어진다. 특정 날짜에 주식을 사고 주식을 산 날로부터 특정 날짜 이후에 주식을 판매했을 때 얻을 수 있는 최대 이익값을 반환하는 문제이다.

날짜별로 가격을 탐색하면서 지난 날짜의 주식 가격 중 최소값과, 현재 탐색중인 날짜의 주식값의 차를 계산해 이익값을 구한 뒤 날짜별로 구한 이익값중 최대값을 반환한다.

먼저 최대 이익값을 저장하기 위한 변수와 주식의 최소 가격을 저장하기 위한 변수를 선언한다.
최대 이익이 될 수 있는 가장 작은 값은 주식이 계속해서 하락만 하는 경우, 즉 0이므로 0으로 초기화 하고 주식의 최소 가격은 prices배열의 첫 번째 값으로 초기화 한다

int maxProfit = 0;          // 최대 이익
int minPrice = prices[0];   // 최소 가격

 

배열을 탐색하며 현재 탐색 중인 날의 가격과 최소 가격중 작은 값을 최소 가격으로 설정하고,
현재 가격에서 최소 가격을 뺀 값과 최대 이익값을 비교하여 큰값을 최대 이익으로 설정한다.

for(int price : prices) {
            minPrice = Math.min(price, minPrice);               // 현재 가격과 최소 가격 중 작은 값을 최소 가격으로 설정
            maxProfit = Math.max(price - minPrice, maxProfit);  // 현재 가격에서 최소 가격을 뺀 값과 최대 이익값 중 큰 값을 최대 이익으로 설정
}

 

탐색이 모두 종료 되면 최대 이익값을 반환한다.

return maxProfit; // 최대 이익값 리턴

 

최종 코드

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;          // 최대 이익
        int minPrice = prices[0];   // 최소 가격
        
        for(int price : prices) {
            minPrice = Math.min(price, minPrice);               // 현재 가격과 최소 가격 중 작은 값을 최소 가격으로 설정
            maxProfit = Math.max(price - minPrice, maxProfit);  // 현재 가격에서 최소 가격을 뺀 값과 최대 이익값 중 큰 값을 최대 이익으로 설정
        }
        
        return maxProfit; // 최대 이익값 리턴
    }
}

---