Bu soru buldum, ve O(N^2 * P): daha iyi bir algoritma ile gelmedi

Verilen bir vektörün P doğal sayılar (1,2,3,...,P) ve başka bir vektörün uzunluğu N olan unsurlardır ilk vektör bul en uzun subsequence ikinci vektör, gibi tüm unsurları eşit dağıtılmış (aynı frekans).

Örnek : (1,2,3) ve (1,2,1,3,2,1,3,1,2,3,1). Uzun subsequence içinde aralığı [2,10], çünkü içerdiği tüm elemanları ilk sıra ile aynı frekans (1 görünür üç kere 2, üç kere 3, üç kere).

Zaman karmaşıklığı O(N * P) olmalıdır.

"Subsequence" genellikle bitişik olmayan anlamına gelir. Kastettiğini varsayıyorum"". alt liste

İşte O(N P) algoritmasıbiz varsayarsak karma(varsayım gerekli değil; sıralamak yerine, sayı tabanı) edebiliriz. Dizideki her sayı için bir çalışan toplam tutmak tarama. Senin örneğin

  1  2  3
 --------
  0  0  0
1 
  1  0  0
2
  1  1  0
1
  2  1  0
3
  2  1  1
2
  2  2  1
1
  3  2  1
3
  3  2  2
1
  4  2  2
2
  4  3  2
3
  4  3  3
1
  5  3  3

Şimdi, asgari eleman çıkararak her satır normalleştirmek. Sonucudur

 0: 000
 1: 100
 2: 110
 3: 210
 4: 100
 5: 110
 6: 210
 7: 100
 8: 200
 9: 210
10: 100
11: 200.

İki karma, göründüğü ilk dizin için her satır eşleme ve göründüğü son indeks hazırlayın. Anahtarlar içinde yineleme ve en büyük olan son bir - ilk.

000: first is at 0, last is at 0
100: first is at 1, last is at 10
110: first is at 2, last is at 5
210: first is at 3, last is at 9
200: first is at 8, last is at 11

En iyi 100 anahtar, alt liste olduğundan uzunluğu 9'dur. Bu alt liste 10 (1 1)inci unsurdur.

Bu çalışır çünkü listesini dengeli ve bu onun ilk ve son normalleştirilmemiş çubuk aynı kadar ekleme sabit, hangi oluşur ve bu ilk ve son normalize histogram ile aynı.