返回介绍

solution / 1000-1099 / 1027.Longest Arithmetic Subsequence / README

发布于 2024-06-17 01:03:32 字数 4187 浏览 0 评论 0 收藏 0

1027. 最长等差数列

English Version

题目描述

给你一个整数数组 nums,返回 nums 中最长等差子序列的长度

回想一下,nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ,且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]0 <= i < seq.length - 1) 的值都相同,那么序列 seq 是等差的。

 

示例 1:

输入:nums = [3,6,9,12]
输出:4
解释: 
整个数组是公差为 3 的等差数列。

示例 2:

输入:nums = [9,4,7,2,10]
输出:3
解释:
最长的等差子序列是 [4,7,10]。

示例 3:

输入:nums = [20,1,15,3,10,5,8]
输出:4
解释:
最长的等差子序列是 [20,15,10,5]。

 

提示:

  • 2 <= nums.length <= 1000
  • 0 <= nums[i] <= 500

解法

方法一:动态规划

我们定义 $f[i][j]$ 表示以 $nums[i]$ 结尾且公差为 $j$ 的等差数列的最大长度。初始时 $f[i][j]=1$,即每个元素自身都是一个长度为 $1$ 的等差数列。

由于公差可能为负数,且最大差值为 $500$,因此,我们可以将统一将公差加上 $500$,这样公差的范围就变成了 $[0, 1000]$。

考虑 $f[i]$,我们可以枚举 $nums[i]$ 的前一个元素 $nums[k]$,那么公差 $j=nums[i]-nums[k]+500$,此时有 $f[i][j]=\max(f[i][j], f[k][j]+1)$,然后我们更新答案 $ans=\max(ans, f[i][j])$。

最后返回答案即可。

如果初始时 $f[i][j]=0$,那么我们需要在最后返回答案时加上 $1$。

时间复杂度 $O(n \times (d + n))$,空间复杂度 $O(n \times d)$。其中 $n$ 和 $d$ 分别是数组 $nums$ 的长度以及数组 $nums$ 中元素的最大值与最小值的差值。

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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文