0060MediumArrayBinary SearchDynamic ProgrammingLongest Increasing Subsequence

Longest Rising Anomaly Pick

Tracked in this browser only

Trains the technique from

LeetCode 300Longest Increasing Subsequence

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_rising_pick(anomalies: list[int]) -> int:

Java

public int longestRisingPick(int[] anomalies)

The intended approach

Time O(n log n)Space O(n)

Keep one array `ends` where `ends[i]` is the smallest anomaly that can close a publishable pick of length `i + 1`. That array stays sorted, so each new anomaly is placed by binary search: it either extends `ends` by one slot, or it overwrites the first entry that is not below it, which makes picks of that length easier to continue later. The final length of `ends` is the answer.

Pythonentry point: longest_rising_pick

def longest_rising_pick(anomalies):
    from bisect import bisect_left
    ends = []
    for value in anomalies:
        slot = bisect_left(ends, value)
        if slot == len(ends):
            ends.append(value)
        else:
            ends[slot] = value
    return len(ends)

The obvious version

For each year, compare it against every earlier year and store the best pick that can end there, then take the largest. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_rising_pick(anomalies):
    n = len(anomalies)
    if n == 0:
        return 0
    best_here = [1] * n
    for i in range(n):
        for j in range(i):
            if anomalies[j] < anomalies[i] and best_here[j] + 1 > best_here[i]:
                best_here[i] = best_here[j] + 1
    return max(best_here)

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in