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 ie buy one and sell one share of the stock design an algorithm to find the maximum profit example 1 input 7 1 5 3 6 4 output 5 max difference 61 5 not 71 6 as selling price needs to be larger than buying price example 2 input 7 6 4 3 1 output 0 in this case no transaction is done i e max profit 0 on2 time type prices listint rtype int on time input 7 1 5 3 6 4 diff x 6 4 2 3 2 type prices listint rtype int o n 2 time type prices list int rtype int o n time input 7 1 5 3 6 4 diff x 6 4 2 3 2 type prices list int rtype int
def max_profit_naive(prices):
    
    max_so_far = 0
    for i in range(0, len(prices) - 1):
        for j in range(i + 1, len(prices)):
            max_so_far = max(max_so_far, prices[j] - prices[i])
    return max_so_far



def max_profit_optimized(prices):
    
    cur_max, max_so_far = 0, 0
    for i in range(1, len(prices)):
        cur_max = max(0, cur_max + prices[i] - prices[i-1])
        max_so_far = max(max_so_far, cur_max)
    return max_so_far