Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Algorithmic Puzzle: Continuous Increasing Subsequences (bor0.wordpress.com)
1 point by bor0 on April 9, 2021 | hide | past | favorite | 1 comment


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




Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: