Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1027.html

1027. Longest Arithmetic Sequence (Medium)

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

Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Note:

1. 2 <= A.length <= 2000
2. 0 <= A[i] <= 10000

Related Topics:
Dynamic Programming

Solution 1. DP

// OJ: https://leetcode.com/problems/longest-arithmetic-sequence/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        unordered_map<int, unordered_map<int, int>> m;
        int ans = 0;
        for (int n : A) {
            m[n] = {};
            for (auto &p : m) {
                int d = n - p.first;
                ans = max(ans, m[n][d] = p.second.count(d) ? p.second[d] + 1 : 2);
            }
        }
        return ans;
    }
};

• Java
• C++
• Python
• Go

• class Solution {
      public int longestArithSeqLength(int[] A) {
          if (A == null)
              return 0;
          int length = A.length;
          if (length <= 2)
              return length;
          int maxLength = 2;
          Map<Integer, TreeSet<Integer>> numIndicesMap = new HashMap<Integer, TreeSet<Integer>>();
          for (int i = 0; i < length; i++) {
              int num = A[i];
              TreeSet<Integer> indices = numIndicesMap.getOrDefault(num, new TreeSet<Integer>());
              indices.add(i);
              numIndicesMap.put(num, indices);
              if (indices.size() > maxLength)
                  maxLength = indices.size();
          }
          for (int i = 0; i < length; i++) {
              int num1 = A[i];
              for (int j = i + 1; j < length; j++) {
                  int num2 = A[j];
                  int difference = num2 - num1;
                  if (difference == 0)
                      continue;
                  int curLength = 2;
                  int prevIndex = j;
                  int prevNum = num2;
                  while (true) {
                      int curNum = prevNum + difference;
                      TreeSet<Integer> indices = numIndicesMap.getOrDefault(curNum, new TreeSet<Integer>());
                      Integer curIndex = indices.ceiling(prevIndex);
                      if (curIndex == null)
                          break;
                      curLength++;
                      prevIndex = curIndex;
                      prevNum = curNum;
                  }
                  maxLength = Math.max(maxLength, curLength);
              }
          }
          return maxLength;
      }
  }
  
  ############
  
  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;
      }
  }
  

• // OJ: https://leetcode.com/problems/longest-arithmetic-sequence/
  // Time: O(N^2)
  // Space: O(N^2)
  class Solution {
  public:
      int longestArithSeqLength(vector<int>& A) {
          unordered_map<int, unordered_map<int, int>> m;
          int ans = 0;
          for (int n : A) {
              m[n] = {};
              for (auto &p : m) {
                  int d = n - p.first;
                  ans = max(ans, m[n][d] = p.second.count(d) ? p.second[d] + 1 : 2);
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def longestArithSeqLength(self, nums: List[int]) -> int:
          n = len(nums)
          dp = [[1] * 1001 for _ in range(n)]
          ans = 0
          for i in range(1, n):
              for j in range(i):
                  d = nums[i] - nums[j] + 500
                  dp[i][d] = max(dp[i][d], dp[j][d] + 1)
                  ans = max(ans, dp[i][d])
          return ans
  
  ############
  
  # 1027. Longest Arithmetic Subsequence
  # https://leetcode.com/problems/longest-arithmetic-subsequence/
  
  class Solution:
      def longestArithSeqLength(self, nums: List[int]) -> int:
          dp = {}
          n = len(nums)
          
          for i in range(n):
              for j in range(i + 1, n):
                  dp[(j, nums[j] - nums[i])] = dp.get((i, nums[j] - nums[i]), 1) + 1
          
          return max(dp.values())
  
  

• 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
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

All Problems

All Solutions