Show problems as
Classic problem #300MediumArrayBinary SearchDynamic ProgrammingLongest Increasing Subsequence

Longest Increasing Subsequence

Real-world version: Longest Rising Anomaly Pick
Tracked in this browser only
Read Longest Increasing Subsequence on LeetCode(opens in a new tab)

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

Learn the pattern firstOptimal Substructure · Dynamic Programming, animated step by step

A weather station files one temperature anomaly per year, in tenths of a degree, and an anomaly may be below zero. anomalies lists them oldest year first.

An analyst wants to publish as many of those years as possible in the order they happened, under one rule: each published anomaly has to be strictly above the one published before it. Years may be left out freely, so the published years need not be neighbours in the list.

Report how many years the largest publishable pick holds.

Examples

Example 1

Input
anomalies = [-3, 8, -1, 12, 4, 15]
Output
4

Publishing the years holding -3, -1, 4 and 15 keeps every step above the one before it. No pick of five years manages that.

Example 2

Input
anomalies = [5, 5, 5, 5]
Output
1

Equal anomalies cannot follow one another because each step has to be strictly above the last, so only a single year is publishable.

Example 3

Input
anomalies = [9, 6, 2, -4]
Output
1

Every later anomaly sits below its predecessor, so no two years can be published together.

Constraints

  • 1 <= anomalies.length <= 2500
  • -10^4 <= anomalies[i] <= 10^4

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_rising_pick(anomalies: list[int]) -> int:
Java
public int longestRisingPick(int[] anomalies)

More on the same topics