Algorithm

Problem Name: 1027. Longest Arithmetic Subsequence

Problem Link: https://leetcode.com/problems/longest-arithmetic-subsequence/
 

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

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int longestArithSeqLength(int[] nums) {
    int result = 2;
    Map < Integer, Integer>[] dp = new HashMap[nums.length];
    for (int i = 0; i  <  nums.length; i++) {
      dp[i] = new HashMap<>();
      for (int j = 0; j  <  i; j++) {
        int diff = nums[i] - nums[j];
        dp[i].put(diff, dp[j].getOrDefault(diff, 1) + 1);
        result = Math.max(result, dp[i].get(diff));
      }
    }
    return result;
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [3,6,9,12]

Output

x
–
+
cmd
4

#2 Code Example with Javascript Programming

Code - Javascript Programming


const longestArithSeqLength = function(A) {
  let a = A
  let n = A.length
  if (n <= 2) return n;

  let i, j, k, d;
  let mxl = 2;
  let current;
  let last;

  //i will be the index of first element of the ap
  for (i = 0; i  <  n - mxl; i++) {
    //j will be the index of second element of the ap
    for (j = i + 1; j  <  n - mxl + 1; j++) {
      //common difference
      d = a[j] - a[i];
      last = a[j];
      current = 2;

      for (k = j + 1; k  <  n; k++) {
        if (a[k] - last == d) {
          //here is our element
          current++;
          last = a[k];
        }
      }

      mxl = Math.max(mxl, current);
    }
  }

  return mxl;
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [3,6,9,12]

Output

x
–
+
cmd
4

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def longestArithSeqLength(self, A: List[int]) -> int:
        dp = collections.defaultdict(int)
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a, b = A[i], A[j]
                dp[b - a, j] = max(dp[b - a, j], dp[b - a, i] + 1)
        return max(dp.values()) + 1
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [9,4,7,2,10]

Output

x
–
+
cmd
3
Advertisements

Demonstration

Previous
#1026 Leetcode Maximum Difference Between Node and Ancestor Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1028 Leetcode Recover a Tree From Preorder Traversal Solution in C, C++, Java, JavaScript, Python, C# Leetcode