Medium

题目描述

给你一个整数数组 nums。

你的任务是找到 nums 的最长子序列 seq 的长度，使得连续元素之间的绝对差值形成一个非递增的整数序列。换句话说，对于 nums 的子序列 seq0, seq1, seq2, ..., seqm，需要满足 |seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm-1|。

返回这样的子序列的长度。

示例 1：

输入：nums = [16,6,3]
输出：3
解释：最长子序列是 [16, 6, 3]，相邻绝对差值为 [10, 3]。

示例 2：

输入：nums = [6,5,3,4,2,1]
输出：4
解释：最长子序列是 [6, 4, 2, 1]，相邻绝对差值为 [2, 2, 1]。

示例 3：

输入：nums = [10,20,10,19,10,20]
输出：5
解释：最长子序列是 [10, 20, 10, 19, 10]，相邻绝对差值为 [10, 10, 9, 9]。

约束条件：

  • 2 <= nums.length <= 10^4
  • 1 <= nums[i] <= 300

提示：

  • 使用动态规划
  • 为每个索引和每个可能的差值存储最大答案

解题思路

解题思路

这是一道典型的动态规划问题。我们需要找到最长的子序列，使得相邻元素的绝对差值非递增。

核心思想

定义状态：dp[i][diff] 表示以 nums[i] 结尾、前一个相邻差值为 diff 的最长子序列长度。

状态转移

对于每个位置 i，我们枚举之前的所有位置 j（其中 j < i）：

  1. 计算当前相邻差值：curr_diff = |nums[i] - nums[j]|
  2. 枚举所有可能的前一个差值 prev_diff
  3. 如果 prev_diff >= curr_diff，则可以进行状态转移： dp[i][curr_diff] = max(dp[i][curr_diff], dp[j][prev_diff] + 1)

初始化和边界处理

  • 初始化：每个单独的元素都可以作为长度为1的子序列开始
  • 对于每对相邻元素，它们可以组成长度为2的子序列

优化考虑

由于数值范围较小（1-300），差值最大为299，可以直接用二维数组存储状态，避免使用哈希表的开销。

最终答案是所有 dp[i][diff] 中的最大值。

时间复杂度为 O(n²×D)，其中 D 是最大可能差值，空间复杂度为 O(n×D)。

代码实现

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = nums.size();
        int maxDiff = 300; // 最大可能的差值
        
        // dp[i][diff] 表示以nums[i]结尾，前一个相邻差值为diff的最长子序列长度
        vector<vector<int>> dp(n, vector<int>(maxDiff + 1, 1));
        
        int result = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int currDiff = abs(nums[i] - nums[j]);
                
                // 直接从j转移到i，长度为2
                dp[i][currDiff] = max(dp[i][currDiff], 2);
                
                // 从j的所有可能差值转移
                for (int prevDiff = currDiff; prevDiff <= maxDiff; prevDiff++) {
                    if (dp[j][prevDiff] > 1) {
                        dp[i][currDiff] = max(dp[i][currDiff], dp[j][prevDiff] + 1);
                    }
                }
                
                result = max(result, dp[i][currDiff]);
            }
        }
        
        return result;
    }
};

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        n = len(nums)
        max_diff = 300  # 最大可能的差值
        
        # dp[i][diff] 表示以nums[i]结尾，前一个相邻差值为diff的最长子序列长度
        dp = [[1] * (max_diff + 1) for _ in range(n)]
        
        result = 1
        
        for i in range(1, n):
            for j in range(i):
                curr_diff = abs(nums[i] - nums[j])
                
                # 直接从j转移到i，长度为2
                dp[i][curr_diff] = max(dp[i][curr_diff], 2)
                
                # 从j的所有可能差值转移
                for prev_diff in range(curr_diff, max_diff + 1):
                    if dp[j][prev_diff] > 1:
                        dp[i][curr_diff] = max(dp[i][curr_diff], dp[j][prev_diff] + 1)
                
                result = max(result, dp[i][curr_diff])
        
        return result

public class Solution {
    public int LongestSubsequence(int[] nums) {
        int n = nums.Length;
        int maxDiff = 300; // 最大可能的差值
        
        // dp[i,diff] 表示以nums[i]结尾，前一个相邻差值为diff的最长子序列长度
        int[,] dp = new int[n, maxDiff + 1];
        
        // 初始化
        for (int i = 0; i < n; i++) {
            for (int diff = 0; diff <= maxDiff; diff++) {
                dp[i, diff] = 1;
            }
        }
        
        int result = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int currDiff = Math.Abs(nums[i] - nums[j]);
                
                // 直接从j转移到i，长度为2
                dp[i, currDiff] = Math.Max(dp[i, currDiff], 2);
                
                // 从j的所有可能差值转移
                for (int prevDiff = currDiff; prevDiff <= maxDiff; prevDiff++) {
                    if (dp[j, prevDiff] > 1) {
                        dp[i, currDiff] = Math.Max(dp[i, currDiff], dp[j, prevDiff] + 1);
                    }
                }
                
                result = Math.Max(result, dp[i, currDiff]);
            }
        }
        
        return result;
    }
}

var longestSubsequence = function(nums) {
    const n = nums.length;
    const maxDiff = 300; // 最大可能的差值
    
    // dp[i][diff] 表示以nums[i]结尾，前一个相邻差值为diff的最长子序列长度
    const dp = Array(n).fill(null).map(() => Array(maxDiff + 1).fill(1));
    
    let result = 1;
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            const currDiff = Math.abs(nums[i] - nums[j]);
            
            // 直接从j转移到i，长度为2
            dp[i][currDiff] = Math.max(dp[i][currDiff], 2);
            
            // 从j的所有可能差值转移
            for (let prevDiff = currDiff; prevDiff <= maxDiff; prevDiff++) {
                if (dp[j][prevDiff] > 1) {
                    dp[i][currDiff] = Math.max(dp[i][currDiff], dp[j][prevDiff] + 1);
                }
            }
            
            result = Math.max(result, dp[i][currDiff]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法指标复杂度
时间复杂度O(n² × D)，其中 n 是数组长度，D 是最大可能差值（300）
空间复杂度O(n × D)

相关题目