Maximum Product Subarray
nums dizisinin bir alt dizisinin elemanlarını birbiriyle çarp ve herhangi bir alt dizinin verebileceği en büyük çarpımı döndür. Bir alt dizi, aralarında boşluk olmadan ardışık elemanlardan oluşur ve asla boş değildir; bu nedenle yalnızca negatif sayılardan oluşan bir dizinin bile yanıtı vardır. Sıfır ve negatif değerlere izin verilir.
Fonksiyon
- numsinteger-array
- çarpılacak tam sayılar, her biri -10 ile 10 arasında
- Döndürürinteger
- boş olmayan bir alt dizinin en büyük çarpımı
Kısıtlar
1 ≤ nums.length ≤ 2 × 104-10 ≤ nums[i] ≤ 10- Her alt dizinin çarpımı 32 bitlik işaretli bir tam sayıya sığar.
Örnekler
- Girdi
- nums = [2, -5, 3, -2, 0, 4]
- Çıktı
- 60
- Açıklama
- İki negatif birbirini götürür:
2 × -5 × 3 × -2 = 60. 0 diziyi ikiye böler ve diğer taraftaki 4, 60'ı geçemez.
- Girdi
- nums = [-2, 3, -4, -1]
- Çıktı
- 24
- Açıklama
- Dizinin tamamının çarpımı -24'tür, çünkü üç negatif sayı içerir. Son elemanı çıkardığınızda bunlardan ikisi kalır:
-2 × 3 × -4 = 24; bu, ilk elemanı çıkardığınızda elde edeceğiniz 12'den büyüktür.
- Girdi
- nums = [-6, 0, -7]
- Çıktı
- 0
- Açıklama
- 0'ı içermeyen bir alt dizi tek bir negatif sayıdan oluşur ve 0'ı içeren bir alt dizinin çarpımı 0 olur. En iyi seçim
[0]alt dizisidir.
Ek soru
En iyi alt dizinin nerede başlayıp nerede bittiğini de O(n) zamanda ve O(1) alanda nasıl bildirirdin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Toplamlarda sıfırın altına düşen bir ara toplamı atmakta sakınca yoktur. Çarpımlarda ise çok negatif bir çarpım, başka bir negatif sayı geldiği anda en büyük çarpıma dönüşebilir. Şimdiye kadarki en büyük çarpımın yanı sıra neyi hatırlamalısın?
Geçerli indekste sona eren alt dizilere bakın. Bunlar arasındaki en büyük çarpım, ya yalnızca geçerli sayıdır ya da sayının bir adım önce sona eren en büyük çarpımla veya bir adım önce sona eren en küçük çarpımla çarpımıdır.
Mevcut indekste biten bir alt dizinin en büyük ve en küçük çarpımları olan
highvelowdeğerlerini koruyarak dizi boyunca ilerle. Her yeni sayı için önce eski değerlerden iki aday çarpımı da hesapla, ardından ikiliyi güncelle ve şimdiye kadar gördüğün en iyihighdeğerini hatırla.
Çözüm
Negatif bir sayıyla çarpmak çarpımların sırasını tersine çevirir; bu nedenle o ana kadarki en küçük çarpım, bir sonraki adımda en büyük çarpım hâline gelebilir ve sıfır tüm çarpımları sıfırlar. Her indekste bir değer yerine iki değer tut: orada biten bir alt dizinin en büyük ve en küçük çarpımı. Böylece tek bir geçiş yeterlidir.
Her başlangıçtan itibaren her alt diziyi çarpın
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Bir başlangıç indeksi sabitleyin ve son indeksi sağa doğru ilerletirken biriken product değerini her yeni elemanla çarpın. Her adımda bunu en iyi değerle karşılaştırmak, her alt diziyi bir kez kapsar. Yanıt negatif olabileceğinden best değerini nums[0] olarak başlatın.
Yaklaşık n²/2 başlangıç ve bitiş indeksi çifti vardır; her biri için bir çarpma yapılır: 20.000 eleman için 2 × 10^8.
Algoritma
bestdeğerininums[0]olarak ayarla.- Her
startiçinproductdeğerini 1 olarak ayarla. enddeğerinistartkonumundan son indekse kadar ilerlet veproductdeğerininums[end]ile çarp.product,bestdeğerinden büyükse onu kaydet.bestdeğerini döndür.
def maxProduct(nums):
n = len(nums)
best = nums[0]
for start in range(n):
product = 1
for end in range(start, n):
# product is now the product of nums[start..end]
product *= nums[end]
if product > best:
best = product
return bestHer iki uçtan tarayın, sıfırlarda yeniden başlayın
Sezgi
Sıfırlar diziyi sıfır içermeyen parçalara ayırır. Bir parçadaki her değerin mutlak değeri en az 1 olduğundan, daha uzun bir alt dizi daha küçük bir mutlak çarpıma sahip olmaz; yalnızca işaret değişir. Negatif sayıların sayısı çiftse parçanın tamamı en iyisidir. Tekse bir negatif sayı çıkarılmalıdır ve en iyi kesim ilk negatif sayıyı ve ondan önceki her şeyi ya da son negatif sayıyı ve ondan sonraki her şeyi çıkarır. Her iki durumda da parçanın bir soneğini veya önekini tutarsın.
Soldan sağa bir geçiş, biriken çarpımla her öneki kontrol eder ve 0'dan sonra çarpımı 1'e sıfırlar. Sağdan sola bir geçiş her soneki kontrol eder. [-2, 3, -4, -1] üzerinde soldan sağa geçiş -2, -6, 24 ve -24 değerlerini; sağdan sola geçiş ise -1, 4, 12 ve -24 değerlerini görür; dolayısıyla yanıt 24'tür. Bu gerekçenin her sıfır dışı değerin mutlak değerinin en az 1 olmasını gerektirdiğini ve bunun tam sayılar için geçerli olduğunu unutma.
Algoritma
bestdeğerininums[0]olarak,productdeğerini ise 1 olarak ayarla.- Soldan sağa ilerle:
productdeğerini her öğeyle çarp vebestileproductdeğerlerinden büyük olanı tut. product0 olduğunda, sonraki çarpım dizisinin baştan başlaması için onu yeniden 1 olarak ayarla.productdeğerini tekrar 1 olarak ayarla ve aynı ilerlemeyi sağdan sola yap.bestdeğerini döndür.
def maxProduct(nums):
best = nums[0]
# Left to right: the product of every prefix of each zero-free run
product = 1
for num in nums:
product *= num
best = max(best, product)
if product == 0:
product = 1 # a zero ends the run, the next one starts fresh
# Right to left: the product of every suffix of each zero-free run
product = 1
for num in reversed(nums):
product *= num
best = max(best, product)
if product == 0:
product = 1
return bestBurada biten en büyük ve en küçük çarpımı izle
Sezgi
i indeksinde biten her alt dizi ya tek başına nums[i] değeridir ya da nums[i] ile i-1 indeksinde biten bir alt dizinin çarpımıdır. nums[i] negatif olduğunda, bu çarpımların en büyüğü i-1 indeksinde biten en küçük çarpımdan elde edilir. Bu yüzden ikisini de tut: geçerli indekste biten bir alt dizinin en büyük ve en küçük çarpımları olan high ve low. Yeni high, num, high × num ve low × num değerlerinin en büyüğüdür; yeni low ise en küçüğüdür. Yalnızca num değerini almak, sıfırdan sonra diziyi yeniden başlatır.
İlk örnekte, -2 geldiğinde low değeri -30'dur ve -30 × -2 = 60, yanıt olan high değerine dönüşür.
Algoritma
high,lowvebestdeğerlerininums[0]olarak ayarla.- Daha sonraki her
numelemanı içina = high × numveb = low × numdeğerlerini hesapla. num,avebarasındaki en büyük değerihigh, en küçük değerilowolarak ayarla.bestvehigharasındaki büyük değeribestolarak ayarla.bestdeğerini döndür.
def maxProduct(nums):
# high and low: the largest and smallest product of a subarray ending at the current index
high = low = best = nums[0]
for num in nums[1:]:
# Multiply both old values first: a negative num swaps their roles
a = high * num
b = low * num
high = max(num, a, b)
low = min(num, a, b)
best = max(best, high)
return best
Tuzaklar ve uç durumlar
- Yalnızca en büyük çarpımı izlemek. İlk örnekte, -2'nin 60'a dönüştürdüğü -30'u göz ardı ettiği için 60 yerine 4 döndürür.
- Yeni
lowdeğerini, güncellenmişhighdeğerinden hesaplamak. İkisinden herhangi birini değiştirmeden öncehigh × numvelow × numdeğerlerini kaydet. bestdeğerini 0 veya 1 olarak başlatmak. Alt dizi boş olamayacağı için[-3], -3 döndürmelidir.- İki geçişli yöntemin yalnızca sol geçişini çalıştırmak.
[-2, 3, 4]dizisinde -2'den büyük bir değer görmez, ancak son ek olan[3, 4]12 verir. - JavaScript, TypeScript ve Lua'da negatif bir sayıyla 0'ı çarpmak, eksi işaretiyle yazdırılan
-0değerini verir. Döndürmeden önce sonuca 0 ekle.
Sıkça sorulan sorular3
Maksimum Çarpım Alt Dizisinin zaman karmaşıklığı nedir?
Her indekste biten en büyük ve en küçük çarpımı takip etmek O(n) zaman ve O(1) alan gerektirir. İki geçişli önek ve sonek yöntemi de aynı maliyete sahiptir. Her başlangıç noktasından itibaren tüm alt dizileri çarpmak O(n²) zaman gerektirir.
Maximum Product Subarray’da neden minimum çarpıma ihtiyaç duyarsınız?
Negatif bir sayı, önceki indekste biten en negatif çarpımı en büyük çarpıma dönüştürür. Yalnızca en büyük çarpımı tutarsan, ihtiyaç duyduğunda o aday artık elinde olmaz. [3, -2, -4] dizisinde, -4'ten önceki en küçük çarpım -6'dır ve -6 × -4 = 24 yanıttır.
Maksimum Çarpım Alt Dizisi, Maksimum Alt Diziden nasıl farklıdır?
Toplamlarda, negatif bir ara toplam yalnızca zarara yol açar; bu yüzden her indeks için tek bir değer yeterlidir. Çarpımlarda ise negatif bir ara değer, başka bir negatif sayıdan sonra en iyi değer hâline gelebilir ve sıfır her şeyi sıfırlar. Bu nedenle çarpım sürümü, her indekste en büyük ve en küçük çarpımı tutar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def maxProduct(nums):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
nums = [2, -5, 3, -2, 0, 4]
Beklenen Çıktı
60