最長非降子

Question

我有以下的算法效果很好

我試圖解釋在這裏爲自己http://nemo.la/?p=943正是在這裏解釋http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/以及和計算器以及

我想對其進行修改，以產生最長的非單調增加子序列

爲序列30 20 20 10 10 10 10

答案應該是4： 「10 10 10 10」

但是，與nlgn版本的算法，它不工作。初始化s到包含第一元素「30」，並在第二個元素= 20。這開始是發生了什麼：

1. 第一步：30比20。不大於或等於我們發現的最小元素大於20新的S變成了「20」

2. 第二步：20大於或等於20。我們擴展序列和S現在包含「20 20」

3. 第三步： 10不大於或等於20.我們發現大於10的最小元素是「20」。新的S變成「10 20」

，之後旨意永遠長不大，算法將返回2，而不是4

int height[100]; 
int s[100]; 

int binary_search(int first, int last, int x) { 

    int mid; 

    while (first < last) { 

     mid = (first + last)/2; 

     if (height[s[mid]] == x) 
      return mid; 

     else if (height[s[mid]] >= x) 
      last = mid; 

     else 
      first = mid + 1; 
    } 
    return first; /* or last */ 
} 

int longest_increasing_subsequence_nlgn(int n) { 

    int i, k, index; 

    memset(s, 0, sizeof(s)); 

    index = 1; 
    s[1] = 0; /* s[i] = 0 is the index of the element that ends an increasing sequence of length i = 1 */ 

    for (i = 1; i < n; i++) { 

     if (height[i] >= height[s[index]]) { /* larger element, extend the sequence */ 

      index++; /* increase the length of my subsequence */ 
      s[index] = i; /* the current doll ends my subsequence */ 

     } 
     /* else find the smallest element in s >= a[i], basically insert a[i] in s such that s stays sorted */ 
     else { 
      k = binary_search(1, index, height[i]); 

      if (height[s[k]] >= height[i]) { /* if truly >= greater */ 
       s[k] = i; 
      } 
     } 
    } 
    return index; 
} 

Answer 1

要找到最長的非嚴格遞增序列，改變這些條件：

1. 如果A[i]是活動列出的所有最終候選者中最小的，我們將開始長度的新活動列表3210。
2. 如果A[i]是所有活動列表的最終候選者中最大的，我們將克隆最大的活動列表，並將其擴展爲A[i]。
3. 如果A[i]介於兩者之間，我們將找到一個最大結束元素小於A[i]的列表。通過A[i]克隆並擴展此列表。我們將放棄所有與此修改列表長度相同的其他列表。

到：

1. 如果A[i]比最小的所有最終候選人名單活躍的的小，我們將開始長度1新的活動列表。
2. 如果A[i]是所有活動列表的最終候選者中最大的，我們將克隆最大的活動列表，並將其擴展爲A[i]。
3. 如果A[i]介於兩者之間，我們將找到一個最大結束元素爲小於或等於A[i]的列表。通過A[i]克隆並擴展此列表。我們將放棄所有與此修改列表長度相同的其他列表。

爲您的示例序列的第四個步驟應該是：

10不小於10（最小的元素）。我們發現最小的元素小於或等於10（即s[0]==10）。通過10克隆並擴展此列表。丟棄長度爲2的現有列表。新的s變爲{10 10}。

Answer 2

這個問題的一個完全不同的解決方案如下。複製數組並對其進行排序。然後，計算數組中任意兩個元素之間的最小非零差（這將是兩個相鄰數組元素之間的最小非零差），並將其稱爲δ。這一步需要時間O（n log n）。

關鍵的發現是，如果添加0到原來的數組的元素0，δ/n至原始陣列的第二元件，2 δ/n至所述陣列的所述第三元件等，則任何原始數組中的非遞減序列在新數組中成爲嚴格遞增的序列，反之亦然。因此，可以用這種方法轉換數組，然後運行一個標準的最長增加子序列求解器，該求解器在O（n log n）時間運行。該過程的最終結果是用於查找最長非遞減子序列的O（n log n）算法。

例如，考慮30,20,20,10,10,10,10。在這種情況下，δ = 10和n = 7，因此δ/n＆ 1.42。新陣列然後

40, 21.42, 22.84, 14.28, 15.71, 17.14, 18.57 

這裏，LIS是14.28，15.71，17.14，18.57，它映射回10，10，10，10的原始陣列英寸

希望這會有所幫助！

Answer 3

除了binary_search()函數中的問題，您的代碼幾乎可以工作，因爲您需要最長的非遞減序列，所以此函數應返回大於目標元素（x）的第一個元素的索引。將其修改爲此，就可以了。

如果您使用C++，std::lower_bound()和std::upper_bound()將幫助您擺脫這個令人困惑的問題。順便說一句，if語句「if (height[s[k]] >= height[i])」是多餘的。

int binary_search(int first, int last, int x) { 

    while(last > first) 
    { 
     int mid = first + (last - first)/2; 
     if(height[s[mid]] > x) 
      last = mid; 
     else 
      first = mid + 1; 
    } 

    return first; /* or last */ 
} 

Answer 4

只需通過使用詞典對比將最長增加的子序列算法應用於有序對（A [i]，i）。