# Longest Arithmetic Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-arithmetic-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/longest-arithmetic-subsequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
**Companies:** [Snapdeal](https://scaleengineer.com/companies/snapdeal)
---
## Problem
Given an array `nums` of integers, return _the length of the longest arithmetic subsequence in_ `nums`.

**Note** that:

* A **subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
* A sequence `seq` is arithmetic if `seq[i + 1] - seq[i]` are all the same value (for `0 <= i < seq.length - 1`).

**Example 1:**

**Input:** nums = [3,6,9,12]
**Output:** 4
**Explanation:**  The whole array is an arithmetic sequence with steps of length = 3.

**Example 2:**

**Input:** nums = [9,4,7,2,10]
**Output:** 3
**Explanation:**  The longest arithmetic subsequence is [4,7,10].

**Example 3:**

**Input:** nums = [20,1,15,3,10,5,8]
**Output:** 4
**Explanation:**  The longest arithmetic subsequence is [20,15,10,5].

**Constraints:**

* `2 <= nums.length <= 1000`
* `0 <= nums[i] <= 500`

# Approaches
## Brute Force Iteration
This approach exhaustively checks every possible starting pair of elements in the array to form an arithmetic subsequence. For each pair, it determines the common difference and then scans the rest of the array to find subsequent elements that fit the sequence.
**Time:** O(n^3), where n is the number of elements in `nums`. There are three nested loops, each potentially iterating up to n times. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Highly inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The core idea is to fix the first two elements of a potential arithmetic subsequence, which in turn defines the common difference. We iterate through all possible pairs of indices `(i, j)` where `i < j`. For each pair, `nums[i]` and `nums[j]` start a sequence of length 2. The difference is `d = nums[j] - nums[i]`. We then iterate from `k = j + 1` to the end of the array, looking for the next term, which should be `nums[j] + d`. If we find it, we extend the sequence and look for the subsequent term. We keep track of the maximum length found across all starting pairs.

```java
class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        if (n <= 2) {
            return n;
        }
        int maxLength = 2;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = nums[j] - nums[i];
                int currentLength = 2;
                int lastElement = nums[j];
                for (int k = j + 1; k < n; k++) {
                    if (nums[k] == lastElement + diff) {
                        currentLength++;
                        lastElement = nums[k];
                    }
                }
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 2, as any pair of numbers forms an arithmetic sequence of length 2.
- Use a nested loop to pick every pair of elements `(nums[i], nums[j])` with `i < j`.
- For each pair, calculate the common difference `d = nums[j] - nums[i]`.
- Start a sequence with these two elements, so `currentLength = 2` and `lastElement = nums[j]`.
- Iterate through the rest of the array from index `j + 1`.
- If an element `nums[k]` is found such that `nums[k] == lastElement + d`, increment `currentLength` and update `lastElement` to `nums[k]`.
- After checking all elements for the current pair, update `maxLength = max(maxLength, currentLength)`.
- Return `maxLength`.

## Dynamic Programming
This approach uses dynamic programming to build up solutions for longer arithmetic subsequences from shorter ones. We maintain a DP table where `dp[i]` stores information about all arithmetic subsequences ending at index `i`.
**Time:** O(n^2), where n is the number of elements. This is due to the two nested loops. HashMap operations take average O(1) time. · **Space:** O(n^2). In the worst case, `dp[i]` can have `i` distinct differences. The total number of entries across all maps is `1 + 2 + ... + (n-1)`, which is `O(n^2)`.
**Pros:** Significantly more efficient than the brute-force approach.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Requires O(n^2) space, which can be large for n=1000.
### Explanation
The state `dp[i]` will be a hash map where `dp[i][d]` stores the length of the arithmetic subsequence ending at index `i` with a common difference `d`. We iterate through the array with an outer loop for `i` from 0 to `n-1`. For each `i`, we have an inner loop for `j` from 0 to `i-1`. Inside the inner loop, we calculate the difference `d = nums[i] - nums[j]`. The pair `(nums[j], nums[i])` can extend any arithmetic subsequence ending at `j` with the same difference `d`. The length of the new subsequence ending at `i` is `dp[j][d] + 1`. If no such subsequence exists ending at `j`, `(nums[j], nums[i])` forms a new subsequence of length 2. We can model this by `dp[i].put(d, dp[j].getOrDefault(d, 1) + 1)`. The default value of 1 represents the subsequence containing only `nums[j]`. We keep track of the maximum length found during this process.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int maxLength = 2;
        Map<Integer, Integer>[] dp = new HashMap[n];
        
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                int newLength = dp[j].getOrDefault(diff, 1) + 1;
                dp[i].put(diff, newLength);
                maxLength = Math.max(maxLength, newLength);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 2`.
- Create an array of HashMaps, `dp`, of size `n`. `dp[i]` will store `{difference: length}` pairs for subsequences ending at `nums[i]`.
- Iterate `i` from 0 to `n-1`:
  - Initialize `dp[i] = new HashMap<>()`.
  - Iterate `j` from 0 to `i-1`:
    - Calculate `diff = nums[i] - nums[j]`.
    - Get the length of the sequence ending at `j` with this `diff`. `length = dp[j].getOrDefault(diff, 1)`.
    - The new length ending at `i` is `length + 1`.
    - Update `dp[i].put(diff, length + 1)`.
    - Update `maxLength = max(maxLength, length + 1)`.
- Return `maxLength`.

## Optimized DP by Iterating Over Differences
This approach optimizes the DP solution by changing the iteration strategy. Instead of iterating through pairs of indices, we iterate through all possible common differences `d`. For each fixed `d`, we find the length of the longest arithmetic subsequence with that difference in `O(n)` time.
**Time:** O(N * D), where N is the length of `nums` and D is the range of values in `nums`. Here, D is `max(nums) - min(nums)`. The number of differences is `2*D+1`. For the given constraints, this is approximately `1000 * 1001`, which is faster than `O(N^2)`. · **Space:** O(N). For each difference `d`, we use a hash map that can store up to `N` elements. This map is reset for each new difference, so the space is not cumulative.
**Pros:** Most efficient approach for the given constraints.; Better time complexity than the standard O(N^2) DP when the range of values is smaller than N.
**Cons:** Performance is dependent on the range of values in the input array. If values were unbounded, this would be inefficient.
### Explanation
Given that the values in `nums` are constrained to `[0, 500]`, the common difference `d` must be in the range `[-500, 500]`. We can iterate through every possible difference `d` in this range. For a fixed `d`, the problem reduces to finding the longest subsequence `a_1, a_2, ..., a_k` where `a_{i+1} = a_i + d`. This can be solved in a single pass through the `nums` array using a hash map. Let `dp[value]` be the length of the arithmetic subsequence with difference `d` ending with `value`. When we process an element `num` from `nums`, the previous element in the sequence would have been `num - d`. The length of the new sequence ending at `num` is `dp.getOrDefault(num - d, 0) + 1`. We update `dp[num]` with this new length and track the overall maximum length.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int maxLength = 2;
        
        for (int diff = -500; diff <= 500; diff++) {
            Map<Integer, Integer> dp = new HashMap<>();
            for (int num : nums) {
                int prev = num - diff;
                int prevLength = dp.getOrDefault(prev, 0);
                int currentLength = prevLength + 1;
                dp.put(num, currentLength);
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
}
```
### Algorithm
- Determine the range of possible differences. Given `0 <= nums[i] <= 500`, the difference `d` is in `[-500, 500]`.
- Initialize `maxLength = 2`.
- Iterate `d` from -500 to 500:
  - Initialize a HashMap `dp` for the current difference. `dp` maps a value to the length of the AP ending with that value.
  - Iterate through each `num` in the `nums` array:
    - The previous value in the sequence would be `prev = num - d`.
    - The length of the AP ending at `num` is `dp.getOrDefault(prev, 0) + 1`.
    - Update `dp.put(num, ...)` with this new length.
    - Update `maxLength = max(maxLength, dp.get(num))`.
- Return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestArithSeqLength(int[] nums) {
    int n = nums.length;
    int ans = 0;
    int[][] f = new int[n][1001];
    for (int i = 1; i < n; ++i) {
      for (int k = 0; k < i; ++k) {
        int j = nums[i] - nums[k] + 500;
        f[i][j] = Math.max(f[i][j], f[k][j] + 1);
        ans = Math.max(ans, f[i][j]);
      }
    }
    return ans + 1;
  }
}

```

### Python

```python
class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int: n = len(nums) f = [[1] * 1001 for _ in range(n)] ans = 0 for i in range(1, n): for k in range(i): j = nums[i] - nums[k] + 500 f[i][j] = max(f[i][j], f[k][j] + 1) ans = max(ans, f[i][j]) return ans

```

### CPP

```cpp
class Solution {
public:
  int longestArithSeqLength(vector<int> &nums) {
    int n = nums.size();
    int f[n][1001];
    memset(f, 0, sizeof(f));
    int ans = 0;
    for (int i = 1; i < n; ++i) {
      for (int k = 0; k < i; ++k) {
        int j = nums[i] - nums[k] + 500;
        f[i][j] = max(f[i][j], f[k][j] + 1);
        ans = max(ans, f[i][j]);
      }
    }
    return ans + 1;
  }
};

```