Best Time to Buy and Sell Stock II[M,Array,Dynamic Programming,Greedy]

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

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

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

 

Constraints:

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

문제1에 비해 이것 저것 조건이 추가되었다.

SELL BUY를 반복할 수 있다는 것과, 주식은 무조건 최대 1개만 보유할 수 있지만 같은 날에 SELL / BUY를 동시에 할 수도 있다는 것이다.

 

1. Python

DP를 어떻게 쓰는 진 모르겠지만, 일단 나의 사랑 Greedy 입장에선 Python으로 한 번에 문제를 해결했다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        ans = 0
        for i in range(1,n):
            if prices[i-1] < prices[i]:
                ans += prices[i] - prices[i-1]
        return ans

 

장점: 이 코드는 직관적이며, "가격이 상승하는 구간마다 차익을 취한다"는 아이디어를 잘 반영하고 있습니다. 이 접근법은 시간 복잡도가 O(n)이고, 공간 복잡도도 O(1)로 매우 효율적입니다. 개선할 점: 주어진 문제를 해결하는 데 있어 특별한 개선점은 없습니다. 이 문제는 매매의 시점을 정확히 파악하는 것보다, 매일의 상승분을 최대한 수익으로 취하는 것이 중요합니다. 현재 코드는 이 문제를 완벽하게 해결하고 있습니다.

간만에 GPT한테 칭찬을 받으니 좋군..

칭찬은 돼지도 춤추게 한다!

 

그래도 DP를 이용해서 푸는 법을 알아보자

#Python with DP -> 별 장점은 없지만 굳이 한 번 DP개념을 써 보는 것에 의의
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        dp=[[0]*2 for _ in range(n)]

        #initialize
        dp[0][0] = 0    # profit w/o holding stock on 1st day
        dp[0][1] = -prices[0] # with ""

        for i in range(1,n):
            dp[i][0] = max(dp[i-1][0] , dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][1] , dp[i-1][0] - prices[i])
        
        return dp[n-1][0]

 

DP를 어떻게 저렇게 2중으로 설정할 생각을 했을까 참.. 어렵네 

 

2. C wih DP

int maxProfit(int* prices, int pricesSize) {
    int dp[pricesSize][2];

    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    for(int i=1;i<pricesSize;i++){
        dp[i][0] = dp[i-1][0] > dp[i-1][1]+prices[i] ? dp[i-1][0] : dp[i-1][1]+prices[i];
        dp[i][1] = dp[i-1][1] > dp[i-1][0]-prices[i] ? dp[i-1][1] : dp[i-1][0]-prices[i];
    }

    return dp[pricesSize-1][0];
}

 

 

3. C++ with Greedy

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans=0;
        for(int i=1 ; i<prices.size();i++){
            ans += max(0,prices[i]-prices[i-1]);
        }
        return ans;
    }
};