Tek seferlik hisse alım satımı
Görev tanımı
Problem
Sana bir hissenin günlük fiyatlarını tutan bir liste veriliyor; i indeksindeki değer i numaralı günün fiyatı. Bir gün alıp daha sonraki bir gün (aynı gün değil) satabilirsin, en fazla bir kez. Bu tek işlemin getirebileceği en büyük kârı döndür. Hiçbir sonraki gün önceki bir günden yüksek fiyat vermiyorsa 0 döndür; en iyi hamle hiç işlem yapmamaktır.
Örnekler
Input: prices = [8, 3, 6, 1, 9, 4]
Output: 8
Neden: 3 numaralı günde 1'den al, 4 numaralı günde 9'dan sat
Input: prices = [7, 5, 4, 2]
Output: 0
Neden: fiyatlar hep düşüyor, her işlem zarar ettirir
Input: prices = [5]
Output: 0
Neden: edge case: tek gün varken satacak sonraki bir gün yok
İpuçları
0 / 3
Her alış gününü her satış günüyle karşılaştırmak işe yarar ama aynı işi defalarca tekrarlar. Bunun yerine soldan sağa tek bir geçişin neyi aklında tutabileceğini düşün.
Zamanda ileri giderken geçmişe dair yalnız iki bilgi önemli: şimdiye kadar görülen en ucuz fiyat ve şimdiye kadar bulunan en iyi kâr.
Günleri bir kez tara. Her günde önce bugünkü satışın kârını önceki en ucuz fiyata göre hesapla ve rekorunu geçiyorsa sakla; sonra bugün öncekilerin hepsinden ucuzsa en ucuz fiyatı güncelle.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Çözüm
Fiyatları bir kez tararken şimdiye kadar görülen en düşük fiyatı yanında taşı. Bugün satmak, bugünkü fiyat eksi bu minimum kadar kazandırır; bu değeri şimdiye kadarki en iyi kârla karşılaştırmak cevabı hep güncel tutar. Minimumu satışın kârını hesapladıktan sonra güncellemek, alış gününün her zaman satış gününden önceki bir gün olmasını garanti eder. Tek geçiş olduğu için zaman O(n), yalnız iki sayı tutulduğu için alan O(1).
def max_trade_profit(prices):
best = 0 # best profit found so far
cheapest = float("inf") # lowest price seen up to today
for p in prices:
# a sale today is only worth as much as the cheapest earlier buy
best = max(best, p - cheapest)
cheapest = min(cheapest, p)
return best
print(max_trade_profit([8, 3, 6, 1, 9, 4])) # -> 8
print(max_trade_profit([7, 5, 4, 2])) # -> 0
print(max_trade_profit([5])) # -> 0Kodda değil de fikirde mi takıldın? Kadane algoritması bunu anlatıyor.