Hacker News new | ask | show | jobs
Algorithmic Puzzle: Continuous Increasing Subsequences (bor0.wordpress.com)
1 points by bor0 1898 days ago
1 comments

It's much simpler, if there's an increasing run of length k, it contains k(k+1)/2 subruns. So you can just do one pass over the array, keeping track of the length of the current run.

    function f(arr) {
      var j=0, ret=0;
      for (var i=1; i<=arr.length; i++) {
        if (i==arr.length || arr[i]<=arr[i-1]) {
          ret += (i-j)*(i-j+1)/2;
          j = i;
        }
      }
      return ret;
    }