Giriş: 2 boyutlu bir dizi NxN Matris pozitif ve negatif elemanları ile.

Çıktı: Onun toplamı gibi her boyutta bir submatrix tüm olası submatrices arasında maksimum.

Gereklilik: Karmaşıklık için algoritmaO(N^3)

Tarih:Bu Algorithmist, Larry ve Kadane Algoritması bir değişiklik ile sorunu çözmeyi başardımkısmensadece toplama - Java aşağıda belirliyor.
TeşekkürlerErnestoüst-sol, sağ-alt köşe - aşağıda Ruby yani Matrix'in sınırlarını belirleyen bir problemin geri kalanını çözmek için başardı.

Burada yazan kod ile gitmek için bir açıklama. Bu verimli bir şekilde çalışması için iki önemli püf noktaları vardır: (İ) Kandane ve (II) algoritma kullanarak önek toplar. Ayrıca (III) matrix püf noktalarını uygulamak gerekir.

Bölüm I: Kandane algoritması

Kandane algoritması, maksimum toplamı ile bitişik bir subsequence bulmak için bir yoldur. Sağlar max bitişik subsequence bulmak için kaba kuvvet yaklaşımı ile başlayıp Kandane algoritması için optimize düşünün.

Sıra varsayalım:

-1,  2,  3, -2

Kaba kuvvet yaklaşım, sırası aşağıda gösterildiği gibi olası tüm sıraları üreten yürüme mesafesinde. Tüm olasılıkları göz önünde bulundurarak, başlangıç, uzatma, ya da her adımda bir liste son verebiliriz.

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
Possible subsequences:
-1   [sum -1]

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
Possible subsequences:
-1 (end)      [sum -1]
-1,  2        [sum  1]
 2            [sum  2]

At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
Possible subsequences:
-1, (end)       [sum -1]
-1,  2 (end)    [sum -1]
 2 (end)        [sum 2]
-1,  2,  3      [sum 4]
 2,  3          [sum 5]
 3              [sum 3]

At index 3, we consider appending the -2
-1,  2,  3, -2
             ^
Possible subsequences:
-1, (end)          [sum -1]
-1,  2 (end)       [sum  1]
 2 (end)           [sum  2]
-1,  2  3 (end)    [sum  4]
 2,  3 (end)       [sum  5]
 3, (end)          [sum  3]
-1,  2,  3, -2     [sum  2]
 2,  3, -2         [sum  3]
 3, -2             [sum  1]
-2                 [sum -2]

Bu kaba kuvvet yaklaşımı için, sonunda en iyi toplamı, (2, 3) listesini almak, ve işte cevap bu. Ancak bu etkili yapmak için, gerçekten listelerinin her birini tutmaya gerek olmadığını düşünün. Bitmedi bu listelerin dışında, sadece iyi tutmak lazım, diğer herhangi bir daha iyi. Bu listeler dışında, sadece iyi bir tutabilir, ve eğer sona erdi olmayanlardan daha iyidir eğer sadece sona erdi.

Yani, sadece pozisyon bir dizi ne kadar takip ve sum bir dizi tutabilir. Dizi şu şekilde tanımlanır pozisyon: pozisyon[r] r biter ve s ' de başlayan liste kaydını tutar s=. Ve, topla[r] dizin r subsequence biten bir özet verir. Bu yaklaşım Kandane bu algoritma optimize edilmiştir.

Örnek yine bizim ilerleme takip ile bu şekilde çalışıyor:

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
We start a new subsequence for the first element.
position[0] = 0
sum[0] = -1

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
We choose to start a new subsequence because that gives a higher sum than extending.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2


At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
We choose to extend a subsequence because that gives a higher sum than starting a new one.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5

Again, we choose to extend because that gives a higher sum that starting a new one.
-1,  2,  3, -2
             ^
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5
positions[3] = 3     sum[3] = 3

Yine, en iyi toplam 5 listesi ve dizin için dizin 1 2, (2, 3).

Bölüm II: Önek toplar

Bir satır boyunca geçerli toplam hesaplamak için bir yol, her başlangıç bir sonu noktasına için istiyoruz. M toplamı öğeleri sayısıdır O(1) O alan sadece ekleme yerine zaman(m) zamanında toplamını hesaplamak istiyorum. Bazı precomputing zaman bu elde edilebilir. Nasıl burada. Sana bir matris olduğunu varsayalım:

a   d   g
b   e   h 
c   f   i

Bu matris precompute

a      d      g
a b    d e    g h
a b c  d e f  g h i

Bir kere o toplamından boyunca sadece iki değer çıkarılarak sütundaki sonuna kadar herhangi baştan herhangi bir sütun çalışan alabilirsiniz.

Bölüm III: max submatrix bulmak için bir araya Getiren numara

Max submatrix üst ve alt satır olduğunu varsayalım. Bunu yapmak için:

1. Yoksay satır senin altına görmezden satır üst satır yukarıda ve satır.
2. Matrix ne kalır, her sütun kullanarak toplamına düşünün bir dizi (birden fazla satır temsil eden bir satır sıralama) şeklinde. (Bu sıra herhangi bir unsur hızla öneki ile Hesaplaması yaklaşım toplar.)
3. Kandane yaklaşımı en iyi subsequence bu rakam kullanın sıra. Olsun dizinleri sol ve sağ söyleyecektir en iyi submatrix pozisyonları.

Şimdi aslında üst ve alt satır bulmaktan? Sadece tüm olasılıkları deneyin. Herhangi bir üst ve alt kısmında herhangi bir yere koyarak yapabilirsin koyarak deneyin, ve Kandane-temel yordamı çalıştırmak, daha önce her ihtimale nitelendirdi. Max bulduğun zaman, üst ve alt konumunu izlemenize.

Satır ve sütun bulma M satır sayısını nerede O(M^2) alır. Sütun bulma alır N satır sayısı(N) O zaman. Toplam süresi O (^2 * N M). Ve, M=N ise, o zaman gerekli O(N^3).