Show problems as
Classic problem #673MediumArrayDynamic ProgrammingBinary Indexed TreeSegment TreeLongest Increasing Subsequence

Number of Longest Increasing Subsequence

Real-world version: Counting The Longest Rising Gauge Runs
Tracked in this browser only
Read Number of Longest Increasing Subsequence on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A river gauge reports its level against a datum, so a reading may be negative. marks holds one reading per hour, earliest hour first.

A rising run is a pick of one or more readings, kept in the order the hours were logged, in which each reading picked is strictly above the one picked before it. The hours picked need not be consecutive. Two runs are different when they pick different hours, even if the readings they pick happen to match.

Return how many rising runs are as long as the longest rising run in the log.

Examples

Example 1

Input
marks = [-14, 62, 5, 90, 41]
Output
3

The longest rising runs pick three hours: -14, 62, 90 and -14, 5, 90 and -14, 5, 41.

Example 2

Input
marks = [77, 77, 77]
Output
3

No reading is strictly above another, so the longest run picks a single hour, and each of the three hours gives one such run.

Example 3

Input
marks = [-8, -20, 46, -3, 46]
Output
2

The longest runs pick three hours: -20 then -3 then the later 46, and -8 then -3 then that same 46.

Constraints

  • 1 <= marks.length <= 2000
  • -10^6 <= marks[i] <= 10^6
  • The answer is guaranteed to fit in a signed 32-bit integer.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_rise_count(marks: list[int]) -> int:
Java
public int longestRiseCount(int[] marks)

More on the same topics