Show problems as
Classic problem #1027MediumArrayHash TableBinary SearchDynamic Programming

Longest Arithmetic Subsequence

Real-world version: Longest Constant-Step Firing Ladder
Tracked in this browser only
Read Longest Arithmetic Subsequence on LeetCode(opens in a new tab)

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

A glass studio keeps readings, the peak kiln temperature of every firing it has run, listed oldest firing first.

A ladder is a selection of two or more firings, kept in the order they appear in readings, such that the change from each selected firing to the next selected one is the same signed amount every time. The firings in a ladder need not be neighbours in the log, and that shared amount may be negative or zero.

Return the number of firings in the longest ladder the log admits.

Examples

Example 1

Input
readings = [412, 60, 205, 118, 350, 176]
Output
3

The firings reading 60, 118 and 176 rise by 58 from one to the next, so a ladder of three firings is reported.

Example 2

Input
readings = [77, 77, 77, 77]
Output
4

Every firing reads 77, so the whole log is a ladder whose shared change is 0.

Example 3

Input
readings = [8, 500, 26, 44, 0, 62, 494]
Output
4

The firings reading 8, 26, 44 and 62 each sit 18 above the one before, giving four firings in log order.

Constraints

  • 2 <= readings.length <= 1000
  • 0 <= readings[i] <= 500

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_ladder(readings: list[int]) -> int:
Java
public int longestLadder(int[] readings)

More on the same topics