May-13-2020, 06:19 PM
(This post was last modified: May-13-2020, 06:19 PM by mrapple2020.)
I resolved the problem below. It seems this is (O(n)) = n^2.
In case you have a more efficient way to resolve it, kindly let me know. Thanks.
#################################################################################
In case you have a more efficient way to resolve it, kindly let me know. Thanks.
#################################################################################
#Imagine an array of ith element is the price of a given stock on day i. #If you were only permitted to complete at most one transaction (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. #Input: [7,1,5,3,6,4] #Output:5 #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. def BuySell(array): #Retrieve elements, condition is that buy operation must happen before selling date best = 0 for i in range (len(array)): for j in range (len(array)): if ( array.index(array[i]) < array.index(array[j]) ): profit = abs( array[i] - array[j] ) if (array[i] < array[j]): #Retrieve the best profit between buying and selling the stock if (profit > best): best = profit return (f'Buy at ${array[i]} Sold at ${array[j]} Profit:${best}') return def main(): array = [7,1,5,3,6,4] print(BuySell(array)) if __name__ == "__main__": main()