[Leetcode 121] 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

 

1) Brute Force

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # 뒤의 값 - 앞의 값이 최대인 값 구하기.
        # 1) n^2로. 다 확인하면서 최대일 때를 갱신하는 방법.
        
        max_diff = 0;
        for i in range(len(prices)):
            for j in range(i+1, len(prices)):
                if prices[j]-prices[i] > max_diff:
                    max_diff = prices[j]-prices[i]
        return max_diff

prices.length 가 10^5까지 될 수 있기 때문에 복잡도가 10^10이 된다. Time Limit Exceeded.

 

2) Maximum Subset

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 1의 경우, diff = [-6, 4, -2, 3, -2] 이다. 이 배열의 subset의 최대값이 수익 최대값이다.

 

- 1) Kadane’s Algorithm (카데인 알고리즘)

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # 뒤의 값 - 앞의 값이 최대인 값 구하기.
        # 2) diff 구하고, 연속된 값들을 더했을 때 최대인 값을 구하기.
        # -6 4 -2 3 -2
        
        # 2) maximum subset
        # -1) Kadane’s Algorithm (카데인 알고리즘)
        if len(prices) == 1:
            return 0
        diff = []
        for i in range(len(prices)-1):
            diff.append(prices[i+1]-prices[i])

        max_subsum = [diff[0], ]
        for i in range(1, len(diff)):
            max_subsum.append(max(max_subsum[i-1] + diff[i], diff[i]))
        max_subsum.append(0)
        return max(max_subsum)

알고리즘 아이디어

0번째 인덱스 부터 현재 i번째 인덱스까지의 최대 부분합 = max_subsum(i)라고 하면

max_subsum(i) = Max(max_subsum(i-1)+num(i), num(i))

• 만약에 num(i)가 음수면 전자가 최대값이 될 것
• 각 인덱스에서 가질 수 있는 max_subsum중에서 max를 찾으면 전체 subset의 최대값을 구할 수 있음

고려할 것

• 조건에서 prices의 갯수가 1개 이상
  → prices가 1개이면 diff가 아에 없을 수도 있다. len(prices) == 1일 때 0 리턴을 먼저 써줬다.
• 수익을 낼 수 없으면, 즉 양수가 없으면 0으로 리턴
  → max_subsum.append(0)으로 음수만 있을 때 자연스럽게 0을 리턴할 수 있도록 했다.

memo[i] = nums[i];
if(memo[i-1] > 0) memo[i] += memo[i-1];

 

- 2) Divide and Conquer (분할 정복)

 

참고

https://medium.com/@vdongbin/kadanes-algorithm-%EC%B9%B4%EB%8D%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-acbc8c279f29

Kadane’s Algorithm (카데인 알고리즘)

https://wellsw.tistory.com/125

LeetCode 풀기 - 53. Maximum Subarray

https://hezma.tistory.com/7

1-(4) Divide and Conquer-(i) The maximum-subarray problem