Untitled
unknown
python
a year ago
2.4 kB
2
Indexable
Never
""" The cost of a stock on each day is given in an array. Find the maximum profit that you can make by buying and selling on those days. If the given array of prices is sorted in decreasing order, then profit cannot be earned at all. Input: arr[] = {100, 180, 260, 310, 40, 535, 695} Output: 865 Explanation: Buy the stock on day 0 and sell it on day 3 => 310 – 100 = 210 Buy the stock on day 4 and sell it on day 6 => 695 – 40 = 655 Maximum Profit = 210 + 655 = 865 Input: arr[] = {4, 2, 2, 2, 4} Output: 2 Explanation: Buy the stock on day 1 and sell it on day 4 => 4 – 2 = 2 Maximum Profit = 2 """ """ Ok, zauwazyłem że najlepiej kupić kiedy jest najniżej, a sprzedać kiedy jest najdrożej. Czyli w zasadzie można zrobić tak: Znaleźć odcinki które są rosnące w tablicy i kupić na ich poczatku, a sprzedać na końcu. Bedzie trzeba przelecieć całą tablice raz z dwoma wskaźnikami i serią porównań. Algorytm byłby taki: Zróbmy trzy zmienne: buy_point, sell_point i profit które początkowo = 0 1. Ustaw bp i sp na 0 2. Jeśli kolejny element i w arr jest większy od poprzedniego, wtedy sell_point = arr[i] 3. Jeśli kolejny element jest mniejszy: 3.1 Jeśli wcześniej sell_point i buy_point były w tym samym miejscu, to po prostu jedź dalej. 3.2 Jeśli bp i sp były w różnych miejscach, odejmij ich wartości i zapisz w profit 4. Powtarzaj do końca tablicy """ # przykładowa tablica z zadania arr = [100, 180, 260, 310, 40, 535, 695] # Dwa wskaźniki w tablicy + zmienna do liczenia zysku buy_point = arr[0] sell_point = arr[0] profit = 0 # Kolejne dwa wskaźniki do pętli current = 0 next = 1 #print(len(arr)-1) while next <= len(arr): #print(arr[current]) #print("Next:", next, end=" ") if next == len(arr): profit = profit + sell_point - buy_point break elif arr[next] > arr[current]: current += 1 next += 1 sell_point = arr[current] #print("New sell_point", sell_point) else: profit = profit + sell_point - buy_point current += 1 next += 1 buy_point = arr[current] sell_point = arr[current] #print("New buy_point", buy_point) print("Profit to:", profit) print("") print("""Ten algorym ma złożoność obliczeniową: O(N) Gdyż musimy przelecieć po całej tablicy tylko raz Oraz złożoność pamięciową O(1) Gdyż nie tworzymy żadnych nowych struktur danych, tylko zmienne """)