title: longest nondecreasing subsequence in O(nlgn)
body: <p>I have the following algorithm which works well</p>
  
  <p>I tried explaining it here for myself <a href="http://nemo.la/?p=943" rel="noreferrer">http://nemo.la/?p=943</a> and it is explained here <a href="http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/" rel="noreferrer">http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/</a> as well and on stackoverflow as well</p>
  
  <p>I want to modify it to produce the longest non-monotonically increasing subsequence</p>
  
  <p>for the sequence 30 20 20 10 10 10 10</p>
  
  <p>the answer should be 4: "10 10 10 10"</p>
  
  <p>But the with nlgn version of the algorithm it isn't working. Initializing s to contain the first element "30" and starting at the second element = 20. This is what happens:</p>
  
  <ol>
  <li><p>The first step: 30 is not greater than or equal to 20. We find the smallest element greater than 20. The new s becomes "20"</p></li>
  <li><p>The second step: 20 is greater than or equal to 20. We extend the sequence and s now contains "20 20"</p></li>
  <li><p>The third step: 10 is not greater than or equal to 20. We find the smallest element greater than 10 which is "20". The new s becomes "10 20"</p></li>
  </ol>
  
  <p>and s will never grow after that and the algorithm will return 2 instead of 4</p>
  
  <pre><code>int height[100];
  int s[100];
  
  int binary_search(int first, int last, int x) {
  
      int mid;
  
      while (first &lt; last) {
  
          mid = (first + last) / 2;
  
          if (height[s[mid]] == x)
              return mid;
  
          else if (height[s[mid]] &gt;= 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 &lt; n; i++) {
  
          if (height[i] &gt;= 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 &gt;= 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]] &gt;= height[i]) { /* if truly &gt;= greater */
                  s[k] = i;
              }
          }
      }
      return index;
  }
  </code></pre>