[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 <= 105
• 0 <= prices[i] <= 104

Solution 1. 전체 탐색(brute force)

public int maxProfit(int[] prices) {

    // 1. brute force
    int len = prices.length;
    int max = 0;
    for (int i = 0; i < len-1; i++) {
        for (int j = i+1; j < len; j++) {
            max = Math.max(max,prices[j]-prices[i]);
        }
    }
    return max;
}

전체탐색으로 모든 경우의 수를 계산하여 최대값을 반환합니다. 간단다나 시간복잡도가 O(n^2)으로 TimeLimitExceeded가 발생하므로 다른 방법으로 풀어내야 합니다.

• 시간 복잡도 : O(N^2)
• 공간 복잡도 : O(1)

Solution 2. 카데인 알고리즘(Kadane's Algorithm)

public int maxProfit(int[] prices) {

    // 2. Dynamic Programming (Kadane's Algorithm)
		int len = prices.length;
    int maxProfit = 0;
    int minPrice = prices[0];
    for (int i = 1; i < len; i++) {
        int profit = prices[i]-minPrice;        // 현재 팔수 있는 값 - 가장 싸게 산 가격
        maxProfit = Math.max(maxProfit,profit); // 최대 profit 저장
        minPrice = Math.min(minPrice,prices[i]); // 현재 인덱스까지의 싸게 살 수 있는 값
    }
    return maxProfit;
}

다이나믹 프로그래밍 개념 중 Kadane's Algorithm 을 사용하면 쉽게 풀어낼 수 있습니다. 현재 인덱스 전까지의 가장 싸게 살 수 있는 가격(minPrice)를 기억하고 현재 인덱스에서 팔았을때의 profit과 지금까지의 최대 maxProfit을 비교하여 가장 큰 값을 반환합니다.

53. Maximum Subarray 문제와 유사한 문제입니다.

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(1)

Reference

Best Time to Buy and Sell Stock - LeetCode

121. Best Time to Buy and Sell Stock, LeetCode, Algorithm, TwoPoint, Array, Recusion, 릿코드, 알고리즘, 코딩테스트, 코테, 문제풀이