title: Longest non-decreasing monotonic subsequence c++
body: <p>I need to write a program which find the longest non-decreasing subsequence in a sequence of numbers from <em>-10</em> to <em>10<sup>5</sup></em>, so for example if my input is:</p>
  
  <blockquote>
    <p>6 6 6 2 2 7</p>
  </blockquote>
  
  <p>My program will return <em>4</em>, cause of:</p>
  
  <blockquote>
    <p>6 6 6 7</p>
  </blockquote>
  
  <p>If my input is:</p>
  
  <blockquote>
    <p>100 6 6 6 2 2 7</p>
  </blockquote>
  
  <p>My half-way working code will return a <em>4</em> as it should.</p>
  
  <p>But if my input is:</p>
  
  <blockquote>
    <p>100 110 120 6 6 6 2 2 7</p>
  </blockquote>
  
  <p>My program returns <em>3</em>, cause of</p>
  
  <blockquote>
    <p>100 110 120</p>
  </blockquote>
  
  <p>But it should again return <em>4</em>. I really can't track where it goes wrong:</p>
  
  <pre><code>int FindIndex(std::vector&lt;int&gt; &amp;v, int k, int result, int key) {
      while (result-k &gt; 1) {
          int mid = k + (result-k)/2;
          if (v[mid] &gt;= key)
              result = mid;
          else
              k = mid;
      }
      return result;
  }
  
  int main() {
      int n=0;
  
      while(cin &gt;&gt; n) {
          vector&lt;int&gt; v;
          int cur;
          while (cin &gt;&gt; cur) {
              v.push_back(cur);
              if (cin.get() == '\n') {
                  break;
              }
          }
          if (v.size() == 0)
              return 0;
  
          vector&lt;int&gt; holder(v.size(), 0);
          int length = 1; 
  
          holder[0] = v[0];
          for (size_t i = 1; i &lt; v.size(); i++) {
              if (v[i] &lt; holder[0])
                  holder[0] = v[i];
              else if (v[i] &gt;= holder[length-1])
                  holder[length++] = v[i];
              else
                  holder[FindIndex(holder, -1, length-1, v[i])] = v[i];
          }
          cout  &lt;&lt; length &lt;&lt; endl;
      }
      return 0;
   }
  </code></pre>