title: Number of all longest increasing subsequences
body: <p>I'm practicing algorithms and one of my tasks is to count the <strong>number of all longest increasing sub-sequences</strong> for given <em>0 &lt; n &lt;= 10^6</em> numbers. Solution <em>O(n^2)</em> is not an option. </p>
  
  <p>I have already implemented finding a LIS and its length (<a href="http://en.wikipedia.org/wiki/Longest_increasing_subsequence"><strong>LIS Algorithm</strong></a>), but this algorithm switches numbers to the lowest possible. Therefore, it's impossible to determine if sub-sequences with a previous number (the bigger one) would be able to achieve the longest length, otherwise I could just count those switches, I guess. </p>
  
  <p>Any ideas how to get this in about <strong>O(nlogn)</strong>? I know that it should be solved using dynamic-programming.</p>
  
  <p>I implemented one solution and it works well, but it requires two nested loops <em>(i in 1..n) x (j in 1..i-1)</em>.<br>
    So it's <em>O(n^2)</em> I think, nevertheless it's too slow.   </p>
  
  <p>I tried even to move those numbers from array to a binary tree (because in each <em>i</em> iteration I look for all smaller numbers then <em>number[i]</em> - going through elements <em>i-1..1</em>), but it was even slower.</p>
  
  <p>Example tests:  </p>
  
  <pre><code>1 3 2 2 4
  result: 3 (1,3,4 | 1,2,4 | 1,2,4)
  
  3 2 1
  result: 3 (1 | 2 | 3)
  
  16 5 8 6 1 10 5 2 15 3 2 4 1
  result: 3 (5,8,10,15 | 5,6,10,15 | 1,2,3,4)
  </code></pre>