Jak znaleźć najdłuższy podciąg ograniczone

Question

Biorąc pod tablicą, która zawiera n różnych liczb całkowitych, znaleźć najdłuższy podciąg który spełnia:

1. element początek podciągu jest najmniejszym z podciągu.
2. elementem końcowym podciągu jest największy z podciągu.

Np .: 8,1,9,4,7. Odpowiedź jest 1,7.

2,6,5,4,9,8. Odpowiedź to 2,6,4,4,9 lub 2,6,5,4,8.

Oto O(N^2) algorytm:

• Let X być tablica liczb.
• Powtórzyć nad X. Załóżmy, że jesteśmy na indeksie i. Niech Y będzie tablicą, w której Y [j] jest liczbą elementów w (j, i], które są mniejsze niż X [j]. Niech z będzie liczbą elementów w [j, i], które są mniejsze niż X [i]. Jeśli X [j] jest mniejsze niż X [i], możemy uzyskać podciągi o długości z-Y [j], która spełnia ograniczenia.

• Zestaw z na 1. Pętla j z i-1 do 0.

  if X[j] < X[i]: z++; ans = max(ans, z - Y[j]); else Y[j]++;

możemy zrobić lepiej? Myślę, że powinien być algorytm O(NlogN), aby znaleźć maksymalną długość.

Answer 1

Pozwól mi przerobić wyjaśnienie tego algorytmu O (n log n).

Interpretuj elementy sekwencji wejściowej jako punkty w 2D, gdzie współrzędna x jest indeksem, a współrzędna y jest wartością. Szukamy prostokąta zawierającego najwięcej punktów wejściowych, z zastrzeżeniem, że lewy dolny róg i górny prawy róg są punktami wejściowymi. W przypadku częściowego uporządkowania według komponentów lewy dolny róg optymalnego prostokąta jest minimalny, a górny prawy róg jest maksymalny.

Wykonaj dwie liniowe przeciągnięcia, aby znaleźć minimalne i maksymalne punkty. Utwórz drzewo segmentu z wartościami całkowitymi z kluczem, które jest oznaczone jako pierwsze, z operacjami, które (i) przyjmują przedział klawiszy i zwiększają/zmniejszają powiązane wartości oraz (ii) obliczają wartość maksymalną. Algorytm polega na iteracji od lewej do prawej poprzez maksymalne punkty, używając drzewa segmentów do śledzenia, ile punktów wejściowych znajduje się pomiędzy (w odniesieniu do częściowego porządku) każdym punktem minimalnym i bieżącym punktem maksymalnym.

Zarówno minimalne punkty, jak i maksymalne punkty, zmniejszają się, gdy przesuwamy się od lewej do prawej. Załóżmy, że przesuwamy się od maksymalnego punktu (x, y) do następnego maksymalnego punktu (x ', y'). Mamy x < x 'i y' < y. Jak zmieniają się wartości w drzewie segmentów? Ponieważ x < x ', punkty o współrzędnej x w x, x'] nie należą do prostokątów z górnym prawym (x, y), ale mogą należeć do prostokątów z górnym prawym (x ', y'). I odwrotnie, ponieważ y '< y, punkty o współrzędnej y w] y', y] mogą należeć do prostokątów z górnym prawym (x, y), ale nie należą do prostokątów z górnym prawym (x ', y'). Wszystkie pozostałe punkty pozostają nienaruszone.

----+     empty 
    | 
----+---------+ (x, y) 
     removed | 
--------------+-------+ (x', y') 
       | added | 
       |  +----+ 
       |  | | 

Przejdziemy przez potencjalne punkty, jeden po drugim, aktualizując drzewo segmentów. Punkty są sortowane według x; jeśli wykonamy kopię i posortujemy według y podczas inicjalizacji, możemy efektywnie wyliczyć potencjalnie dotknięte punkty. Zauważ, że z czasem przedziały x są rozłączne, podobnie jak przedziały y, więc możemy sobie pozwolić na spędzenie logarytmu w każdym potencjalnie dotkniętym punkcie. Podając punkt (x '', y '') taki, że x '' in] x, x '] (zauważ, że y' '< = y' w tym przypadku), musimy zwiększyć drzewo segmentów w minimalnych punktach którego współrzędna x leży w] inf, x ''], a którego współrzędna y leży w] inf, y '']. Może to nie wyglądać jednowymiarowo, ale w rzeczywistości porządkowanie współrzędnych x i porządkowanie współrzędnych y są przeciwne dla minimalnych punktów, więc ten zestaw kluczy jest interwałem. Podobnie, biorąc pod uwagę punkt (x '' ', y' '') taki, że y '' 'in] y', y] (zauważ, że x '' '< = x w tym przypadku), musimy zmniejszyć wartości w odstępie kluczy.

Oto "magiczna" struktura danych drzewa segmentów w Javie.

public class SegmentTree { 
    private int n; 
    private int m; 
    private int[] deltaValue; 
    private int[] deltaMax; 

    private static int nextHighestPowerOfTwoMinusOne(int n) { 
     n |= n >>> 1; 
     n |= n >>> 2; 
     n |= n >>> 4; 
     n |= n >>> 8; 
     n |= n >>> 16; 
     return n; 
    } 

    public SegmentTree(int n) { 
     this.n = n; 
     m = nextHighestPowerOfTwoMinusOne(n) + 1; 
     deltaValue = new int[m]; 
     deltaMax = new int[m]; 
    } 

    private static int parent(int i) { 
     int lob = i & -i; 
     return (i | (lob << 1)) - lob; 
    } 

    private static int leftChild(int i) { 
     int lob = i & -i; 
     return i - (lob >>> 1); 
    } 

    private static int rightChild(int i) { 
     int lob = i & -i; 
     return i + (lob >>> 1); 
    } 

    public int get(int i) { 
     if (i < 0 || i > n) { 
      throw new IllegalArgumentException(); 
     } 
     if (i == 0) { 
      return 0; 
     } 
     int sum = 0; 
     do { 
      sum += deltaValue[i]; 
      i = parent(i); 
     } while (i < m); 
     return sum; 
    } 

    private int root() { 
     return m >>> 1; 
    } 

    private int getMax(int i) { 
     return deltaMax[i] + deltaValue[i]; 
    } 

    public void addToSuffix(int i, int delta) { 
     if (i < 1 || i > n + 1) { 
      throw new IllegalArgumentException(); 
     } 
     if (i == n + 1) { 
      return; 
     } 
     int j = root(); 
     outer: 
     while (true) { 
      while (j < i) { 
       int k = rightChild(j); 
       if (k == j) { 
        break outer; 
       } 
       j = k; 
      } 
      deltaValue[j] += delta; 
      do { 
       int k = leftChild(j); 
       if (k == j) { 
        break outer; 
       } 
       j = k; 
      } while (j >= i); 
      deltaValue[j] -= delta; 
     } 
     while (true) { 
      j = parent(j); 
      if (j >= m) { 
       break; 
      } 
      deltaMax[j] = 
       Math.max(0, 
         Math.max(getMax(leftChild(j)), 
            getMax(rightChild(j)))); 
     } 
    } 

    public int maximum() { 
     return getMax(root()); 
    } 
}