[LeetCode] 121 Best Time to Buy and Sell Stock

Description

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 <= 10^5
• 0 <= prices[i] <= 10^4

---

풀이

가장 큰 수익을 출력하는 문제. 이득을 보지 못했을 경우 0을 반환한다.

브루트포스 방법으로는 이중 for문으로 각 일자 값에 대해 최대 이익을 구한다.

DP 를 이용하면
for문을 한 번만 돌면서 현재 값이 가장 낮은 값인지, 맞다면 가장 낮은 값을 현재 값으로 변경한다.
가장 낮은 값이 아니라면 현재 이익이 최대 이익보다 큰지 비교하여 최대 이익을 찾게 된다.

---

코드

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = 10001, maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice)
                minPrice = prices[i];
            else if (prices[i] - minPrice > maxProfit)
                maxProfit = prices[i] - minPrice;
        }
        return maxProfit;
    }
    
    public int maxProfitBrute(int[] prices) {
        int maxProfit = 0, profit;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] < prices[j]) {
                    profit = prices[j] - prices[i];
                    if (maxProfit < profit) maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }
}