CP #6 II : Maximum Subarray Divide and Conquer

Daha once O(n) ile cozdugumuz max subarray probleminin, leetcode'da bir de follow up'i var. Problemi divide and conquer ile cozebilir miyiz?

Ilk bakista, verilen dizeyi sol ve sag olarak ikiye ayirip, ayri ayri max sub-array'larini bulmak kolay gozukuyor. Recursive bir fonksiyona bakiyor:

class Solution:
    def maxSubarraySum(self, nums, start, end):
        # base case: sadece tek eleman varsa, max olarak onu dondur
        if start == end:
            return nums[start]
        else:
            # orta noktayi bularak dizeyi ikiye ayirip
            # hangisinin max sub array'i buyukse onu donduruyoruz
            mid = start + (end-start)//2
            return max(self.maxSubarraySum(nums, start, mid), 
                               self.maxSubarraySum(nums, mid+1, end))
    
    def maxSubArray(self, nums):
        return self.maxSubarraySum(nums, 0, len(nums)-1)


Bu cozumde tabi ki bir eksik var. Ya max sub array, bizim boldugumuz yerden geciyorsa? Zaten [-2,1,-3,4,-1,2,1,-5,4] icin calistirdigimizda 4 sonucunu alacagiz cunku suanda sadece tek tek elemanlara bakiyoruz.

[-1, 2, 1, -5]
[-1, 2] vs [1, -5]
([-1] vs [2] ) vs ([1] vs [-5])
(-1 vs 2) vs (1 vs -5]
(2) vs (1)
return 2

Seklinde dizedeki en buyuk elemani getirecektir. Cunku bolme noktalarini da hesaba katmiyoruz. 

Bolunme noktasindan gecen max sub-arrayi nasil bulabiliriz? 

Bolunme noktasini biliyoruz. Bu noktadan sola ve saga, start ve end noktalarina kadar giderek maks sum'i bulabiliriz.

def crossingSubarraySum(self, nums, start, mid, end):
    # sola git
    left_sum = float("-Infinity")
    sm = 0
    for t in range(mid, start-1, -1):
        sm += nums[t]
        left_sum = max(left_sum, sm)
    
    # saga git
    sm = 0
    right_sum = float("-Infinity")
    for k in range(mid+1, end+1):
        sm += nums[k]
        right_sum = max(right_sum, sm)
    
    # nums[crossing] 2 kere saydik
    ret = max(left_sum, right_sum, left_sum+right_sum)
    return ret


Seklinde, bolme noktasindan sola ve saga gitmek suretiyle bir max sub array daha elde etmis oluyoruz. Bu iki metodu birlestirirsek,

class Solution:
    def maxSubarraySum(self, nums, start, end):
        # base case: sadece tek eleman varsa, max olarak onu dondur
        if start == end:
            return nums[start]
        else:
            # orta noktayi bularak dizeyi ikiye ayiriyoruz
            # soldaki max sub array, sagdaki max sub array ve de 
            # bolunme noktasindan gecen max sub array'den buyuk olani donduruyoruz
            mid = start + (end-start)//2
            return max(self.maxSubarraySum(nums, start, mid), 
                               self.maxSubarraySum(nums, mid+1, end),
                               self.crossingSubarray(nums, start, mid, end))
    
    def maxSubArray(self, nums):
        return self.maxSubarraySum(nums, 0, len(nums)-1)

Analiz
Onceki cozum O(n) olmasi itibari ile elbette ki daha performansli. Her adimda dizeyi ikiye boldugumuzden dolayi O(nlogn) olmaktadir. 

Yorumlar

Yorum Gönder

Bu blogdaki popüler yayınlar

Python'da Multithreading ve Multiprocessing

Resim
Bu multithreading isini cok karistirdilar.  Thread ve Process Thread ve Process, birbirinden bagimsiz olarak calisabilen (teorik olarak) kod parcaciklaridir.  Aradaki fark, ayni program tarafindan olusturulan threadler ayni hafiza alanina erisebilir. Buna karsilik process kendi basina bagimsiz bir program olarak dusunulebilir, Kendine ait hafiza alani vardir.  Bu da demek oluyor ki, thread'ler kendi aralarinda haberlesebilmek icin ekstra bir efora ihtiyac duymazken, process'leri birbiri ile konusturabilmek icin ekstra birseler (gRPC?) yapmak gerekir. Yukarida ayni program tarafindan olusturulan threadler derken bile, aslinda buradaki program, bir process 'tir. Her process primary thread olarak adlandirilan en azindan 1 adet thread'e sahiptir. (Single threaded tabirini hatirlayalim).  Peki neden birden fazla thread'e ihtiyac duyalim?  Kullanici acisindan, birden fazla process'in ayni anda calistirilbilmesi demek, ayni anda birden fazla uygulamayi calistirabilme...
Devamı

SD #1: Scalability

Resim
Bir websitesi host ettigimizi dusunelim. Gidecegimiz yer bir hosting sirketi olacaktir. Bu hosting sirketi genellikle birden fazla musteriyi belki de ayni makine uzerinde host etmektedir. Birgun gelip de web sitemiz cok populer olursa, artik bu donanim ile web siteye erisim imkansiz ya da cok yavas bir hale gelebilir. Burada iki secenek var: 1- Vertical scaling: Yani daha fazla ram, cpu, disk. Elimizdeki donanimi artirmak. Ornek olarak fazladan bir cpu core'a sahip olmak demek, ayni anda birden fazla requeste gercekten paralel olarak cevap verebilmemize olanak taniyacaktir. Tek bir cpu core ile paralel islem yapmak olanaksizdir. Simdilerde bulmak zor ama tek core olan bilgisayarlarda bile ayni anda birden fazla is yapabiliyoruz. Ama aslinda isletim sistemi her bir uygulama icin cpu'dan sirayla hizmet aliyor ve biz bunu paralelmis gibi algiliyoruz.   Ancak burada bir limit var. Bir bilgisayarin donanimini en fazla belirli bir olcude artirabilirsiniz. Bir noktadan sonra maliyer...
Devamı

Threat Modeling 1

Resim
- Tum modeller yanlistir, bazilari kullanisli. (Ronaldinho, 2024, survivor, Dominican Republic) Nedir? - Modelleme bize bir sistemi gorsellestirme imkani taniyarak, sistemi daha iyi anlamamizi saglar. - Iyi bir model bizim; ne uzerinde calistigimizi,  nelerin yanlis gidebilecegini  ve bizim bu yanlis gidebilecek hususlar hakkinda ne yapabilecegimizi daha iyi anlamamizi saglar. Ne zaman yapilir? - Ne kadar erken baslarsak o kadar iyidir - Penetrasyon testi yapacak olan kisiler de genellikle bizim olusturdugumuz bu treat modelini referans alirlar. - Sprintin bir parcasi olarak yapilabilir. Feature'lar implemente edilirken paralel olarak de treat modelleri olusturulabilir. Nasil yapilir? Bir yazilim muh olarak tasarladigimiz sistemlerin confidentiality , integrity ve availability ozelliklerini maksimumda tutmak bizim gorevimizdir. Threat modeling icin birden fazla yol vardir. Nasil ki programlama dilleri farkli trade-off'lara sahipse ve yerine gore bazilari daha kullanisli...
Devamı