# LeetCode 1027: Longest Arithmetic Subsequence

## Problem Restatement

We are given an integer array `nums`.

We need to return the length of the longest arithmetic subsequence in `nums`.

A subsequence is arithmetic if the difference between consecutive elements is constant.

The official constraints state that `2 <= nums.length <= 1000` and `0 <= nums[i] <= 500`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `nums` |
| Output | Length of the longest arithmetic subsequence |
| Subsequence | Not necessarily contiguous; indices must be increasing |

Function shape:

```python
def longestArithSeqLength(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [3, 6, 9, 12]
```

The whole array is arithmetic with difference `3`.

Answer:

```python
4
```

Example 2:

```python
nums = [9, 4, 7, 2, 10]
```

Subsequence `[4, 7, 10]` with difference `3`.

Answer:

```python
3
```

Example 3:

```python
nums = [20, 1, 15, 3, 10, 5, 8]
```

Subsequence `[20, 15, 10, 5]` with difference `-5`.

Answer:

```python
4
```

## Key Insight

Use DP where `dp[i][d]` is the length of the longest arithmetic subsequence ending at index `i` with common difference `d`.

For each pair `(j, i)` with `j < i`:

```python
d = nums[i] - nums[j]
dp[i][d] = dp[j].get(d, 1) + 1
```

## Algorithm

1. Create `dp` as a list of dictionaries.
2. For each index `i`, for each `j < i`:
   - Compute `d = nums[i] - nums[j]`.
   - `dp[i][d] = dp[j].get(d, 1) + 1`.
3. Track the maximum value across all `dp[i][d]`.

## Correctness

`dp[j].get(d, 1)` returns the length of the best arithmetic subsequence ending at `j` with difference `d`, or `1` if no such subsequence exists (just the single element `nums[j]`). Adding `1` accounts for `nums[i]`.

By considering all pairs, every possible arithmetic subsequence is captured.

## Edge Cases

- Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
- Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
- When the target is absent, the loop should still terminate and return the problem-specific failure value.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | All pairs `(j, i)` |
| Space | `O(n^2)` | DP dictionaries |

## Common Pitfalls

- Do not mix inclusive and half-open bounds inside the same loop.
- Make sure each branch strictly reduces the search interval.

## Implementation

```python
class Solution:
    def longestArithSeqLength(self, nums: list[int]) -> int:
        dp = [{} for _ in range(len(nums))]
        best = 2

        for i in range(1, len(nums)):
            for j in range(i):
                d = nums[i] - nums[j]
                dp[i][d] = dp[j].get(d, 1) + 1
                best = max(best, dp[i][d])

        return best
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.longestArithSeqLength([3, 6, 9, 12]) == 4
    assert s.longestArithSeqLength([9, 4, 7, 2, 10]) == 3
    assert s.longestArithSeqLength([20, 1, 15, 3, 10, 5, 8]) == 4
    assert s.longestArithSeqLength([0, 8, 45, 88, 48, 68, 28, 55, 17, 24]) == 2

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[3,6,9,12]` | `4` | Uniform difference of 3 |
| `[9,4,7,2,10]` | `3` | `[4,7,10]` |
| `[20,1,15,3,10,5,8]` | `4` | `[20,15,10,5]` |