Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:


Input: [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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.


Example 2:


Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Difficulty: introductory

Starter code:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        

Solutions:
class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         n = len(prices)
         if n <=1:
             return 0
         else:
             minprice = prices[0]
             res = 0
             for i in range(1,n):
                 if prices[i] - minprice > res:
                     res = prices[i] - minprice
                 if prices[i]<minprice:
                     minprice = prices[i]
 
             return res
                     
             
         


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         hold = float("inf")
         result = 0
         
         for p in prices:
             if p>hold:
                 result=max(result,p-hold)
             hold = min(hold, p)
         return result


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices:
             return 0
         mincur,maxcur=prices[0],0
         for index in range(len(prices)):
             mincur=min(prices[index],mincur)
             maxcur=max(prices[index]-mincur,maxcur)
         return maxcur


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if len(prices) < 2:
             return 0
         max_profit = 0
         min_before = prices[0]
         for i in prices:
             min_before = min(i,min_before)
             max_profit = max(max_profit,i-min_before)
 
         return max_profit

class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         profit = 0
         buy = prices[0] if prices else None
         for price in prices:
             buy = min(buy, price)
             profit = max(profit, price - buy)
         return profit
             


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         hold = float("inf")
         result = 0
         
         for p in prices:
             if p>hold:
                 result=max(result,p-hold)
             else:
                 hold = p
         return result


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         curr_min = float('inf')
         max_profit = 0
         
         for price in prices:
             curr_min = min(curr_min, price)
             profit = price - curr_min 
             max_profit = max(max_profit, profit)
             
         return max_profit

class Solution:
     def maxProfit1(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices:
             return 0
         mincur,maxcur=prices[0],0
         for index in range(len(prices)):
             mincur=min(prices[index],mincur)
             maxcur=max(prices[index]-mincur,maxcur)
         return maxcur
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if len(prices)<2:
             return 0
         maxcur,maxpro=0,0
         for index in range(1,len(prices)):
             maxcur+=(prices[index]-prices[index-1])
             maxcur=max(0,maxcur)
             maxpro=max(maxpro,maxcur)
         return maxpro


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         profit = 0
         for i in range(len(prices)-1):
             for j in range(i+1,len(prices),1):
                 if prices[i] >= prices[j]:
                     break
                 else:
                     profit = max(profit, prices[j]-prices[i])
         return profit

class Solution:
     def maxProfit(self, prices):
         max_profit = 0
         local_max = 0
         for i in range(1,len(prices)):
             if(local_max+prices[i]-prices[i-1]>0):
                 local_max += prices[i]-prices[i-1]
                 if(local_max>max_profit):
                     max_profit = local_max
             else:
                 local_max = 0
         return max_profit


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         n = len(prices)
 
         return self.count_profit(prices,0,n -1)
 
     
 
     def count_profit(self,prices,left,right):
         if left >= right:
             return 0
         if right - left == 1:
             profit = prices[right] - prices[left]
             if profit < 0:
                 profit = 0
             return profit
         mid = (left + right) // 2
         pro_left = self.count_profit(prices,left,mid)
         pro_right = self.count_profit(prices,mid+1,right)
         pro_mid = 0
         i = min(prices[left:mid + 1])
         j = max(prices[mid+1:right + 1])
         pro_mid = j -i
         profit = max(pro_left,pro_mid,pro_right)
         if profit < 0:
             profit = 0
         return profit
 
 
 
 


class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         # find the valley first, them sale at peak
         if not prices: return 0
         min_price = prices[0]
         max_profit = 0
         for i in prices:
             if i < min_price:
                 min_price = i
             elif max_profit < i - min_price:
                 max_profit = i - min_price
         return max_profit

class Solution:
     def maxProfit(self, prices):
         """
         :type prices: List[int]
         :rtype: int
         """
         if not prices: return 0
         min_val = prices[0]
         profit = 0
         for i in range(1, len(prices)):
             if profit < prices[i] - min_val:
                 profit = prices[i] - min_val
             if prices[i] < min_val:
                 min_val = prices[i]
 
         return profit