Show problems as
Classic problem #3872MediumArrayEnumeration

Longest Arithmetic Sequence After Changing At Most One Element

Real-world version: Longest Evenly Spaced Stretch After One Re-cut
Tracked in this browser only
Read Longest Arithmetic Sequence After Changing At Most One Element on LeetCode(opens in a new tab)

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

A survey crew has driven markers along a rail line and written down readings, where readings[i] is the distance recorded at marker i, in order along the line.

A stretch is a block of markers at consecutive positions of readings. A stretch is evenly spaced when the difference between each pair of neighbouring readings inside it is the same throughout. A stretch of one or two markers is evenly spaced, since it has no pair of differences to disagree.

Before measuring, the crew may re-cut at most one marker: choose at most one index of readings and replace its reading with any integer you like, which may be negative and may repeat another reading. Only one index may be replaced in total.

Return the number of markers in the longest evenly spaced stretch that exists after the re-cut.

Examples

Example 1

Input
readings = [3, 6, 9, 20, 15, 18]
Output
6

Re-cut marker 3 to 12. The readings become 3, 6, 9, 12, 15, 18, where every neighbouring pair differs by 3, so all six markers sit in one evenly spaced stretch.

Example 2

Input
readings = [1, 5, 2, 9]
Output
3

Re-cut marker 2 to 9. Markers 0, 1 and 2 then read 1, 5, 9, a stretch of three whose neighbouring readings differ by 4 throughout.

Example 3

Input
readings = [50, 1, 4, 7, 10]
Output
5

Re-cut marker 0 to -2. The readings become -2, 1, 4, 7, 10, spaced 3 apart the whole way, so the stretch covers all five markers. A replacement reading is allowed to be negative.

Constraints

  • 4 <= readings.length <= 10^5
  • 1 <= readings[i] <= 10^5
  • The replacement reading may be any integer, and is not restricted to the range above.

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

More on the same topics