1027. Longest Arithmetic Subsequence

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Recall that a subsequence of an array nums is a list nums[i1], nums[i2], …, nums[ik] with 0 <= i1 < i2 < … < ik <= nums.length - 1, and that a sequence seq is arithmetic if seq[i+1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

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

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    
    
    /*
    
    12 - 9
    12 - 6
    12 - 3
    
     9 - 6
     9 - 3
     
     6 - 3
    
    0:
        9 - 1
        3 - 4
    1:
        6 - 3
        3 - 3
    2:
        3 - 2
        6 - 2
    3:  
        3 - 1
        6 - 1
        9 - 1
    
    */
    
    public int longestArithSeqLength(int[] nums) {
        Map<Integer, Integer>[] maps = new HashMap[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            maps[i] = new HashMap<Integer, Integer>();
        }
        
        int max = 0;
        
        for (int j = nums.length - 1; j >= 0; j--) {
            for (int i = j - 1; i >= 0; i--) {
                int diff = nums[j] - nums[i];
                maps[i].put(diff, maps[j].getOrDefault(diff, 1) + 1);
                max = Math.max(max, maps[i].get(diff));
            }
        } 
        
        
        return max;
    }
}

Solution#

Solution