Untitled

"""
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
""")