Problem Statement

Given an array nums containing positive integers, return the maximum length of a subsequence that forms an arithmetic progression.

• A subsequence is an array that can be formed from nums by deleting 0 or more elements without changing the order of the remaining elements.

• An arithmetic progression (AP) is a sequence of numbers in which the difference between any two consecutive elements is constant. In short, seq[i + 1] - seq[i] should be same for all 0 <= i < seq.length - 2.

Examples

• Example 1:

  • Input: [8, 12, 6, 4, 2]
  • Expected Output: 4
  • Justification: The subsequence [8, 6, 4, 2] forms the longest arithmetic subsequence with a common difference of -2, thus the longest arithmetic subsequence has a length 4.

• Example 2:

  • Input: [5, 10, 15, 7, 11, 5]
  • ****Expected Output: 3
  • Justification:** The subsequence [5, 10, 15] forms the longest arithmetic subsequence with a common difference of 5.

• Example 3:

  • Input: [1, 7, 10, 15, 27, 29]
  • Expected Output: 3
  • Justification: The subsequence [1, 15, 29] forms the longest arithmetic subsequence with a common difference of 14.

Try it yourself

Try solving this question here: