title: Finding number of length 3 increasing (or decreasing) subsequences?
body: <p>Given an array of positive integers, how can I find the number of increasing (or decreasing) subsequences of length <code>3</code>? E.g. <code>[1,6,3,7,5,2,9,4,8]</code> has <code>24</code> of these, such as <code>[3,4,8]</code> and <code>[6,7,9]</code>.</p>
  
  <p>I've found solutions for length <code>k</code>, but I believe those solutions can be made more efficient since we're only looking at <code>k = 3</code>.</p>
  
  <p>For example, a naive <code>O(n^3)</code> solution can be made faster by looping over elements and counting how many elements to their left are less, and how many to their right are higher, then multiplying these two counts, and adding it to a sum. This is <code>O(n^2)</code>, which obviously doesn't translate easily into <code>k &gt; 3</code>.</p>