Hadi tamsayılar kümesi var. Bu set en uzun artan subsequence dinamik programlama kullanarak bulmak istiyorum. Bu sadece pratik, benim algoritmalar eski ders notlarımı gözden geçiriyor, ve bu nasıl çalıştığını anlamak için görünmüyor.

TAMAM, ilk N kümesi boyutunu nerede O(N^2), hangi en basit çözümü anlatacağım. Aynı zamanda da anlatacağım(N log N) O bir çözüm var. here bölümünde bunun için Verimli algoritmalar bak.

Dizinin indis N-1 0 olarak kabul edecektir. Bu yüzden DP tanımlayalım[i] dizin ile biten element olan LİS(en Uzun artan subsequence) uzunlukta olacak. DP tüm bakıyoruz hesaplamak için indis j < ben ve hem de eğer DP kontrol[j] 1 >DP[i] ve dizi[j] < dizi[i](artan olmak istiyoruz). Eğer bu doğruysa DP[i] için geçerli optimum güncelleme yapabiliriz. Dizi için genel optimum bulmak için DP maksimum değer[0..N-1] alabilirsin.

int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i  )
{
   DP[i] = 1;
   prev[i] = -1;

   for (int j = i - 1; j >= 0; j--)
      if (DP[j]   1 > DP[i] && array[j] < array[i])
      {
         DP[i] = DP[j]   1;
         prev[i] = j;
      }

   if (DP[i] > maxLength)
   {
      bestEnd = i;
      maxLength = DP[i];
   }
}

Dizi prev gerçek dizisi bulmak daha sonra mümkün değil, sadece onun uzunluğu kullanıyorum. Sadece geri yinelemeli bir döngü önceki kullanarak[bestEnd] bestEnd. -1 değeri durdurmak için bir işarettir.

TAMAM, daha verimli ** 5 çözüm:

S[pos] uzunluk artan dizi pos biten en küçük tam sayı olarak tanımlanmış olsun.

Şimdi her tam sayı ile giriş seti X yineleme ve aşağıdakileri yapın:

1. X >S, son öğe S sonuna X ekleyin. Bu essentialy 13* *yeni büyük bir bulduk demektir.

2. Aksi takdirde X, daha >= S, en küçük elemanı Bul ve değiştir X. S herhangi bir zamanda sıralanmış olduğundan, öğe log(N) ikili arama kullanarak bulunabilir.

Toplam N tamsayılar ve her biri - N * log(N) = O(N log N) ikili arama zamanı

Şimdi gerçek bir örnek verelim:

Kümesinin tamsayılar: 2 6 3 4 1 2 9 5 8

Adımlar:

0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS

Bu LİS uzunluğu kadar 5 (S boyut).

Daha üst bir dizi kullanacağız LIS gerçek yeniden. parent[i] dizin öğe LIS son i dizin i ile eleman selefi olsun.

İşleri kolaylaştırmak için, dizinin devam edebiliriz S gerçek sayılar değil, ama onların endeksleri(pozisyonları). {1, 2, 4, 5, 8} ama {4, 5, 3, 7, 8} devam etmiyoruz.

Giriş[4] =1giriş[5] =2giriş[3] =4giriş[7] =5giriş[8] =8.

Biz düzgün ana dizi güncelleme, gerçek LİS

input[S[lastElementOfS]], 
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................

Önemli şey - ne kadar üst güncelleme yapacağız şimdi dizi? İki seçenek vardır:

1. X >S parent[indexX] = indexLastElement son eleman. Bu yeni öğenin üst son öğe olduğu anlamına gelir. Biz sadece S sonuna X önüne.

2. Aksi takdirde X daha >=*, 38*, en küçük öğenin dizinini Bul ve değiştir X. Burada parent[indexX] = S[index - 1].