[1, 3, 5, 7, 9] Output: 5 Explanation: Whole array is in subsequence.

Solution

Method 1 - Dynamic Programming

Before solving this problem, let us solve a different problem first.

How to find if a sorted array contains an arithmetic progression of length 3?

This can be done by looping over the array and then finding numbers 'i' and 'k' on either side of current number 'j' such that

arr[j] + arr[k] = 2*arr[i] and
k < i < j

To find the longest AP efficiently, we can use dynamic programming (DP). We'll use a 2D DP table where dp[i][j] represents the length of the longest AP ending with elements at indices i and j. The idea is to iterate over all pairs (i, j) where i < j, and for each pair, we look for the previous element in the AP (

Related Tags