如何找到最長約束子

Question

由於其中含有N個不同的整數數組，找到最長子，其滿足：

1. 子序列的起始單元是最小的子序列。
2. 子序列的結束元素是子序列中最大的元素。

例如： 8,1,9,4,7。答案是1,4,7。

2,6,5,4,9,8。答案是2,6,5,4,9或2,6,5,4,8。

這裏是一個O(N^2)算法：

• 設X是數字的陣列。
• 迭代X。假設我們在索引i。假設Y是其中Y [j]是(j, i]中小於X [j]的元素的數量。假設z是小於X [i]的[j, i]中的元素數目。如果X [j]小於X [i]，我們可以得到滿足約束條件的長度爲z-Y [j]的子序列。

• 設置z至1。 Loop j from i-1 down to 0。

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

我們可以做得更好？我認爲應該有一個O(NlogN)算法來查找最大長度。

Answer 1

讓我重做這個O（n log n）算法的解釋。

將輸入序列的元素解釋爲2D中的點，其中x座標是索引，y座標是值。我們正在尋找包含最多輸入點的矩形，受限於左下角和右上角爲輸入點。在通常的分量偏序下，最優矩形的左下角是最小的，而右上角是最大的。

做兩個線性掃描找到最小值和最大值點。創建一個由前者鍵入的整數值分段樹，其操作（i）接受鍵的間隔並遞增/遞減關聯值並且（ii）計算最大值。該算法是通過最大點從左到右進行迭代，使用分段樹來追蹤每個最小點與當前最大點之間（相對於偏序）的輸入點的數量。

當我們左右移動時，最小點和最大點都會下降。那麼，假設我們從最大點（x，y）移動到下一個最大點（x'，y'）。我們有x < x'和y'< y。段樹中的值如何改變？由於x < x'，x]座標在] x，x']中的點不屬於右上方（x，y）的矩形，但可能屬於右上方（x'，y'）的矩形。相反，由於y'< y，y座標在] y'，y]中的點可能屬於右上角（x，y）的矩形，但不屬於右上角（x'，y'）的矩形。所有其他點都不受影響。

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

我們逐個查看可能受影響的點，更新段樹。點數按x排序;如果我們在初始化過程中複製並按y排序，那麼我們可以有效地枚舉可能受影響的點。請注意，隨着時間的推移，x-區間和y-區間是兩兩不相交的，所以我們可以在每個可能受影響的點上花費對數時間。給定一個點（x''，y''），使得x''in] x，x']（注意在這種情況下y'< = y'），我們需要在最小點處增加分段樹其x座標位於] inf，x「]，其y座標位於] inf，y」]。這看起來可能不是一維的，但實際上，x座標的排序和y座標的排序對於最小點是相反的，所以這組鍵是間隔。類似地，給定一個點（x'''，y'''）使得y'''in] y'，y]（注意在這種情況下x'''''''''''），我們需要遞減值在鍵的間隔。

這是Java中的「魔術」段樹數據結構。

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()); 
    } 
}