Question

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

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

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;
  }
}

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;
  }
};

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
}

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;
}