Settings

Theme

Algorithmic Puzzle: Continuous Increasing Subsequences

bor0.wordpress.com

1 points by bor0 5 years ago · 1 comment

Reader

cousin_it 5 years ago

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

Keyboard Shortcuts

j
Next item
k
Previous item
o / Enter
Open selected item
?
Show this help
Esc
Close modal / clear selection