Algorithmic Puzzle: Continuous Increasing Subsequences(bor0.wordpress.com)

1 pointsby bor05 tahun yang lalu1 comments

bor0.wordpress.com

Algorithmic Puzzle: Continuous Increasing Subsequences

https://bor0.wordpress.com/2021/04/09/algorithmic-puzzle-continuous-increasing-subsequences/

1 comments

cousin_it5 tahun yang lalu

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;
    }