Skip to content

1027. Longest Arithmetic Subsequence

Description

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

Solutions

Solution 1: Dynamic Programming

We define \(f[i][j]\) as the maximum length of the arithmetic sequence ending with \(nums[i]\) and having a common difference of \(j\). Initially, \(f[i][j]=1\), that is, each element itself is an arithmetic sequence of length \(1\).

Since the common difference may be negative, and the maximum difference is \(500\), we can uniformly add \(500\) to the common difference, so the range of the common difference becomes \([0, 1000]\).

Considering \(f[i]\), we can enumerate the previous element \(nums[k]\) of \(nums[i]\), then the common difference \(j=nums[i]-nums[k]+500\), at this time \(f[i][j]=\max(f[i][j], f[k][j]+1)\), then we update the answer \(ans=\max(ans, f[i][j])\).

Finally, return the answer.

If initially \(f[i][j]=0\), then we need to add \(1\) to the answer when returning the answer.

The time complexity is \(O(n \times (d + n))\), and the space complexity is \(O(n \times d)\). Where \(n\) and \(d\) are the length of the array \(nums\) and the difference between the maximum and minimum values in the array \(nums\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func longestArithSeqLength(nums []int) int {
    n := len(nums)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, 1001)
    }
    ans := 0
    for i := 1; i < n; i++ {
        for k := 0; k < i; k++ {
            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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function longestArithSeqLength(nums: number[]): number {
    const n = nums.length;
    let ans = 0;
    const f: number[][] = Array.from({ length: n }, () => new Array(1001).fill(0));
    for (let i = 1; i < n; ++i) {
        for (let k = 0; k < i; ++k) {
            const 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;
}

Comments