CP #7 : Best Time to Buy and Sell Stock Problemi

 Problem surada.

Cozum

Ilk etapta yine naive implementasyon ile basyalabiliriz. Brute force ile dizedeki her bir noktada alinip, ondan sonra gelen bir noktada satldiginda elde edilecek kari hesaplayip, max olani dondurebiliriz. Ama bu bizi bir yere goturmez. 

Yapmamiz gereken sey, maksimum farki bulmak. Ama bunu yaparken de kucuk olan sayinin buyuk olan sayidan sonra gelmesini saglamak. 

Diyelim ki dizeyi bastan sona dogru traverse ediyoruz. 

Her adimda, gecmisteki en kucuk rakami tutabiliriz. Burasi alis noktasi olacak. 

Yine ayni adimda, eger bu noktada satmis olsaydik, (ve tabi daha onceki adimlardan bu adima kadar olan dize elemanlari icerisinde en dusuk olani bulmusuzdur) ne kadar kar edecektik bunu hesapliyoruz. 

Eger simdiye kadar buldugumuz profitlerden yuksek ise, bunu global maks olarak atiyoruz. 

def maxProfit(self, prices):

    maks = float("-Infinity")

    past_min = float("Infinity")

    for p in prices:

        # simdiye kadar gorulen en dusuk degeri guncelle

        past_min = min(past_min, p)

        

        # bu noktada satmis olsa idik ne kadar kar ederdik?

        # simdiye kadar edilmis karlardan buyuk ise, guncelle

        maks = max(maks, p - past_min)

    return maks

Analiz

Tum dizeyi sadece bir kere dolastigimiz icin O(n) kompleksiteye sahibiz. Hafiza gereksinimi ise sadece maks ve past_min degerlerini tutmak icin iki degisken, bu da O(1)'e tekabul ediyor.

Follow-up

Peki bir kere alip bir kere satmak yerine istedigimiz kadar alip satabilseydik, max profiti nasil hesaplardik? Surada ikinci soru var.

Iki ornegi inceleyelim. maxProfit([1,2,3,4,5]) icin, sonuc 4 cunku birinci gun alip sonuncu gun satmaktan baska yol yok. Yani surekli artis var ise, beklemek gerekiyor.

maxProfit([7,1,5,3,6,4]) burada ise 1de alip 5'te satmak ve 3'te alip 6'da satmak gerekiyor. Yani dususlerde alip, artislarda satmamiz max profiti getiriyor. Bu durumda problem sadece artislari toplamaya indirgenmis oluyor. 

class Solution:

    def maxProfit(self, prices):        

        profit = 0

        for i in range(1, len(prices)):

            if prices[i] > prices[i-1]:

                profit += prices[i] - prices[i-1]

        return profit

Kompleksite ayni sekilde O(n) ve hafiza ise O(1).