1027.最长等差数列

链接：1027.最长等差数列
难度：Medium
标签：数组、哈希表、二分查找、动态规划
简介：给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

题解 1 - cpp

• 编辑时间：2023-04-22
• 执行用时：268ms
• 内存消耗：138.1MB
• 编程语言：cpp
• 解法介绍：dp[i][j]表示以i为结尾，公差为j的最大序列长度。

class Solution {
    public:
        int longestArithSeqLength(vector<int>& nums) {
            int n = nums.size(), res = 0;
            vector<vector<int>> dp(n, vector<int>(1005, 0));
            for (int i = 0; i < n; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    int num = nums[i] - nums[j] + 500;
                    dp[i][num] = max(dp[i][num], dp[j][num] + 1);
                    res = max(res, dp[i][num]);
                }
            }
            return res + 1;
        }
    };

题解 2 - python

• 编辑时间：2023-04-22
• 执行用时：2916ms
• 内存消耗：22.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        dp = [[0] * 1005 for _ in range(n)]
        for i in range(n):
            for j in range(i-1, -1, -1):
                num = nums[i] - nums[j] + 500
                dp[i][num] = max(dp[i][num], dp[j][num] + 1)
                res = max(dp[i][num], res)
        return res + 1

题解 3 - rust

• 编辑时间：2023-04-22
• 执行用时：40ms
• 内存消耗：5.9MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn longest_arith_seq_length(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = 0;
        let mut dp = vec![vec![0; 1005]; n];
        for i in 0..n {
            for j in (0..i).rev() {
                let num = (nums[i] - nums[j] + 500) as usize;
                dp[i][num] = dp[i][num].max(dp[j][num] + 1);
                res = res.max(dp[i][num]);
            }
        }
        res + 1
    }
}