×

Welcome to TagMyCode

Please login or create account to add a snippet.
0
0
 
0
Language: Python
Posted by: ls sean
Added: Sep 15, 2021 3:54 PM
Modified: Sep 15, 2021 3:55 PM
Views: 3046
Tags: array dp
  1. '''
  2. https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
  3.  
  4. You are given an array prices where prices[i] is the price of a given stock on the ith day.
  5.  
  6. 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.
  7.  
  8. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
  9.  
  10.  
  11.  
  12. Example 1:
  13.  
  14. Input: prices = [7,1,5,3,6,4]
  15. Output: 5
  16. Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
  17. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
  18. Example 2:
  19.  
  20. Input: prices = [7,6,4,3,1]
  21. Output: 0
  22. Explanation: In this case, no transactions are done and the max profit = 0.
  23.  
  24.  
  25. Constraints:
  26.  
  27. 1 <= prices.length <= 105
  28. 0 <= prices[i] <= 104
  29. '''
  30.  
  31. from sorting.sorting_util import SortingUtil
  32. import snoop
  33. class Solution(object):
  34.     @snoop
  35.     def maxProfit(self, prices):
  36.         '''
  37.        https://leetcode.com/submissions/detail/555147168/
  38.        slow
  39.        Runtime: 1480 ms
  40. Memory Usage: 22.8 MB
  41.        '''
  42.         """
  43.        :type prices: List[int]
  44.        :rtype: int
  45.        """
  46.         res,buy = 0,float('inf')
  47.         for price in prices:
  48.             buy = min(price,buy)
  49.             res = max(res,price-buy)
  50.         return res
  51.     @snoop
  52.     def maxProfit2(self, prices):
  53.         '''
  54.        https://leetcode.com/submissions/detail/555151528/
  55.        Runtime: 788 ms, faster than 98.03% of Python online submissions for Best Time to Buy and Sell Stock.
  56. Memory Usage: 22.7 MB, less than 29.77% of Python online submissions for Best Time to Buy and Sell Stock.
  57.        '''
  58.         prof = 0
  59.         best_time = prices[0]
  60.         for i in prices:
  61.             if i<best_time:
  62.                 best_time = i
  63.             else:
  64.                 if i - best_time> prof :
  65.                     prof = i- best_time
  66.         return prof
  67.  
  68. if __name__ == '__main__':
  69.     #arr = SortingUtil.generate_random_array(5)
  70.     arr = [2,6,4,8,10,9,15]
  71.     #arr = [1]
  72.     #arr = [-1]
  73.     #print(Solution().productExceptSelf(arr))
  74.     print(Solution().maxProfit2(arr))
  75.