475. Counting the Increasing Runs
Count the contiguous non-empty runs that are STRICTLY increasing. A run of one element counts, since it has no pair to violate the condition.
1 3 5 4 4 6 -> 10
5 4 3 2 1 -> 5 every single element, and nothing longer
Problem #452 finds the LENGTH of the longest increasing subsequence. This one counts, and counts runs rather than subsequences, so almost nothing carries over except the habit of asking what to accumulate.
## Counting by right endpoint
Every run has exactly one last element, so grouping the runs by that element counts each
one once and none twice. The number of increasing runs ENDING at index i is the length
of the increasing stretch ending at i:
run = run + 1 if a[i] > a[i-1], else 1
total += run
Summing run over all i is the answer, and no formula is needed.
## Why not the closed form
A maximal increasing stretch of length m contains m(m+1)/2 runs, so you can split
the array into maximal stretches and add m(m+1)/2 for each. That is the same number
and is equally fine. The running version is shorter and has one fewer place to put an
off-by-one, which is the honest reason to prefer it.
## What the tests pin down
The comparison is STRICT, so equal neighbours end a stretch. 1 2 2 3 answers 6, not
10: the stretches are 1 2 and 2 3, each contributing 3. A solution using >=
answers 10 and looks perfectly plausible.
5 4 3 2 1 answers 5 and 1 1 1 1 answers 4. Both are "no run longer than one", and
a solution that starts run at 0 rather than 1 answers 0 on each.
The count reaches n(n+1)/2, which at n = 200000 is about 2 * 10^10 and needs 64
bits even though the values are small.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ value ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print the number of contiguous non-empty strictly increasing runs.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.