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

https://leetcode.com/problems/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

1. Python

늘 그렇듯, Python으로 dp를 돌리거나 for문을 돌리면 time limit이 뜬다 ㅠㅠ

Naive한 나의 code여...

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [0]*(len(prices))
        for i in range(len(prices)-1,0,-1):
            dp[i] = max(0,prices[i]-min(prices[:i]))
        return max(dp)

 

시간을 더 줄여볼 순 없을까?

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [0]*(len(prices))
        for i in range(len(prices)-1,0,-1):
            if prices[i-1]>prices[i]: continue
            dp[i] = max(0,prices[i]-min(prices[:i]))
        return max(dp)

이런 잔잔바리 기술로는 어림도 없다.

 

알아보니, slicing 을 쓰는 순간 time complexity가 N -> N^2가 된다.(for문 안에 있으니..)

즉 slicing을 쓰면 그냥 시간낭비는 엄청나다는 것. 얘만 안 써도 time limit은 어느정도 커버가 된다.

 

 - W/O DP

#python w/o DP
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minval = 10**4
        maxval = 0
        for x in prices:
            if x < minval:
                minval = x
            if x-minval > maxval :
                maxval = x-minval
        return maxval

 - With DP

# Python with DP
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        dp = [0]*n
        minval = prices[0]

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

 

2. C

DP를 안 써 봄

int max(int a, int b){
    return a > b ? a : b;
}
int min(int a, int b){
    return a < b ? a : b;
}

int maxProfit(int* prices, int pricesSize) {
    // with out using DP
    int minval = prices[0];
    int ans = 0;

    for(int i=1;i<pricesSize;i++){
        ans = max(ans,prices[i]-minval);
        minval = min(minval,prices[i]);
    }

    return ans;
}

 

3. C++

DP를 써 

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> dp(n,0);
        int minval = prices[0];

        for(int i=1;i<n;i++){
            dp[i] = max(dp[i-1],prices[i]-minval);
            minval = min(minval,prices[i]);
        }
        return dp[n-1];
    }
};