N tamsayıları tek bir günde hisse senedi fiyatlarını temsil eden bir dizi verilmiştir sanırım. Bir çift (buyDay, sellDay), buyDay ≤ sellDay, buyDay üzerinde hisse senedi satın aldık ve sellDay sattım, kar maksimize istediğimiz gibi bulmak istiyoruz.

Açıkça vardır, bir O(n²onları tüm dışarı mümkün (buyDay, sellDay ) tüm çiftleri çalışıyor ve en iyisini alarak algoritma çözüm. Ancak, daha iyi bir algoritma O(n) zamanda çalışan bir belki var mı?

Teşekkürler!

Bu sorun seviyorum. Klasik röportaj bir soru aklınıza ne kadar bağlı olarak, daha iyi ve daha iyi çözümler elde bitireceğiz. Büyük ihtimalle O daha iyi(n . bunu yapmak için²) zaman, buradaki sorun hakkında aklınıza gelebilecek üç farklı şekilde listeledim. Umarım bu sorunuza cevap!

İlk olarak, böl-ve-fethet çözüm. Hadi yarım giriş bölerek, her alt dizilim sorun çözme, birlikte iki birleştirerek bunu çözebilecek miyiz. Meğer biz aslında bunu yapmak, ve bunu verimli bir şekilde yapamaz! Sezgi aşağıdaki gibidir. Eğer tek bir gün varsa, en iyi seçenek o gün satın alıp tekrar kar için aynı gün satmak. Aksi takdirde, iki parçaya bölünmüş bir dizi. Eğer en uygun cevabın ne olabileceğini düşünürsek, üç basamak birinde olmalıdır:

1. Doğru satın almak/satmak çifti tamamen ilk yarısı içinde oluşur.
2. Doğru satın almak/satmak çifti tamamen ikinci yarısı içinde oluşur.
3. Doğru satın almak/satmak çifti iki yarısı arasında oluşur - biz ilk yarısında satın almak, ikinci yarısında sat o zaman.

Özyinelemeli olarak birinci ve ikinci yarıya bizim algoritması çağırarak (1) değerleri ve (2) alabiliriz. Seçeneği için (3), en yüksek kar elde etmenin yolu ilk yarısında en düşük noktada satın almak ve ikinci yarısında en büyük satış noktası. Sadece basit bir doğrusal giriş üzerinde tarama yapıyor ve iki değer bularak iki yarısı düşük ve en yüksek değerleri bulabiliriz. Bu da bize aşağıdaki nüks ile bir algoritma verir:

T(1) <= O(1)
T(n) <= 2T(n / 2)   O(n)

Tekrarını çözmek için Master Theorem kullanarak, bu(n lg n) zamanında çalışır ve yinelemeli çağrılar için(lg n) O boşluk kullanın. Sadece naif Ç(n . yendik ^sup>2) çözüm!

Ama bekleyin! Bundan daha iyi yapabiliriz. Bizim nüks(n) vadeli elimizdeki tek sebebi tüm giriş her yarım düşük ve en yüksek değerlerini bulmaya tarama yapmak zorundaydık dikkat edin. Zaten yinelemeli olarak her yarım araştırıyoruz beri, belki daha iyi özyineleme, minimum ve maksimum değerleri her yarım saklanan eli geri alarak yapabiliriz! Diğer bir deyişle, bizim özyineleme üç şey elleri geri:

1. Ve kat kar etmek satın almak satmak.
2. En düşük değer aralığında genel olarak.
3. En büyük değer aralığında genel olarak.

Bu son iki değerleri yinelemeli olarak aynı anda çalıştırılması basit bir özyineleme kullanarak hesaplamak için özyineleme (1) olarak ifade edilebilir:

1. Tek öğeli bir dizi max ve min değerleri sadece unsurudur.
2. Birden çok element bir dizi max ve min değerleri her yarım bölerek yarısını, max ve min değerleri bulmak giriş, sonra ilgili max ve min alarak bulunabilir.

Eğer bu yaklaşımı kullanırsak, nüks ilişkimiz artık

T(1) <= O(1)
T(n) <= 2T(n / 2)   O(1)

Ana Teoremini kullanarak bizi buraya O(lg n) O bir çalışma zamanı(n) verir orijinal çözümümüz daha iyi yer yok!

Ama bir dakika bile bundan daha iyisini yapabiliriz! Bu sorun, dinamik programlama kullanarak çözümü düşünelim. Fikir şu şekilde sorun hakkında düşünmek olacaktır. İlk k elemanları baktıktan sonra sorunun cevabını zaten bildiğini varsayalım. (K 1)st unsur, bizim ilk çözümü ile birlikte, bilgilerimizi (k 1) İlk element için sorunu çözmek için kullanabilir miyiz? Eğer öyleyse, büyük bir algoritması ilk öğenin problemini çözerek gidiyor, o zaman ilk iki, ilk üç, vb alabiliriz. ilk n öğeleri için hesaplanan istediğimiz kadar.

Hadi bunu yapmak için nasıl düşünmek. Eğer sadece bir öğe varsa, biz zaten çift sat/al iyi olmalı. Şimdi ilk k elementleri için en iyi cevap olduğunu varsayalım ve (k 1)st öğesi bak. O zaman tek yolu bu değeri yaratabilmek için bir çözüm daha iyi ne vardı ilk k elemanları ise arasındaki fark, en küçük ilk k elemanlar ve yeni bir unsur daha büyük en büyük fark ettik hesaplanan şimdiye kadar. O yüzden sanırım bu kadar gidiyoruz genelinde unsurları, takibini yapmak, iki değer - en düşük değer gördük şimdiye kadar ve maksimum kar yapabiliriz, ne dersin sadece ilk k elemanları. Başlangıçta, şu ana kadar gördüğümüz en düşük değer ilk unsurudur, ve maksimum kar sıfırdır. Yeni bir element gördüğümüzde ilk yapmak istediğimiz nasıl en düşük fiyat şimdiye kadar gördüğüm ve mevcut fiyata satan satın alarak bilgisayar tarafından optimal kar güncelleştirin. Eğer bu şimdiye kadar hesaplanan ettik en iyi değerden daha iyi ise, o zaman biz de en iyi çözüm bu yeni kar için güncelleme. Sonraki, biz asgari unsur şimdiye kadar geçerli en küçük elemanı asgari olarak görülen güncelleme ve yeni elemanı.

Her adımda(1) iş O olacak ve tam bir kez n elemanlarının her ziyaret olduğumuza göre, bu O(n) tamamlamak için zaman alır! Dahası, sadece O(1) Yedek Depo kullanır. Bu şimdiye kadar kazanılmış ettik kadar iyi!

Senin girdilere örnek olarak, burada bu algoritma çalışabilir. Bu noktada arasında dizinin değerleri sayı değerleri algoritması tarafından düzenlenen karşılık gelir. Aslında bütün bunlar ((n) bellek alacaktı!), mağaza olmazdı ama yararlı algoritma gelişmeye

        5        10         4         6        7
min         5         5        4          4         4    
best      (5,5)     (5,10)   (5,10)     (5,10)    (5,10)

Cevap: (5, 10)

        5        10         4         6        12
min         5         5        4          4         4    
best      (5,5)     (5,10)   (5,10)     (5,10)    (4,12)

Cevap: (4, 12)

        1       2       3      4      5
min         1       1       1      1      1
best      (1,1)   (1,2)   (1,3)  (1,4)  (1,5)

Cevap: (1, 5)

Şimdi daha iyi yapabilir miyiz? Ne yazık ki, asimptotik anlamda değil. Eğer kullanıyoruz az O(n) zaman, yapamayız bak tüm sayılar giriş ve böylece yok garanti vermeyiz Bayan en iyi cevap (biz sadece "gizle" unsurları da bakmadı bile). Artı, O daha az(1) Herhangi bir boşluk kullanamayız. Sabit faktörler büyük-O gösterimi gizli için bazı iyileştirmeler olabilir, ama aksi takdirde radikal bir şekilde daha iyi bir seçenek bulmak için bekleyemeyiz.

Genel olarak, bu aşağıdaki algoritmalar var demektir:

• Saf: O(n²) zaman, O(1) Alanı.
• Böl-ve-Fethet: O(n lg n) zaman, O(lg n) alanı.
• Böl ve yut optimize: O(n) zaman, O(lg n) alanı.
• Dinamik programlama: O(n) zaman, O(1) Alanı.

Bu yardımcı olur umarım!

EDİT: Eğer ilgileniyorsanız, kodlu bulduma Python version of these four algorithmsonlarla birlikte oynayabilir ve göreli performansları yargıç böylece. Tadını çıkarın!