LeetCode_动态规划_中等_1027.最长等差数列

爱被打了一巴掌 2023-10-09 18:59 6阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/longest-arithmetic-subsequence

## 2.思路 ##

（1）动态规划  
思路参考[本题官方题解][Link 1]。

① 设 `minNum` 和 `maxNum` 分别为数组 nums 中的最大值和最小值，那么子序列的公差 `d` 的取值范围为 `[minNum - maxNum, maxNum - minNum]`；

② 枚举所有可能的公差 d，在每次枚举的过程中定义以下 dp 数组并进行初始化，**dp\[i\] 表示以 nums\[i\] 结尾且公差为 d 的最长子序列长度**。

int[] dp = new int[maxNum + 1];
     //因为以 nums[i] 结尾且公差为 d 的最长子序列不一定存在，因此先将其值初始化为 -1，方便后续进行判断
     Arrays.fill(dp, -1);

③ 对于每一个 d，遍历数组 nums 中的每一个元素 num：

*  如果 prev = num - d 未超出数组值范围的边界，并且 dp\[prev\] != -1，则说明以 nums\[prev\] 结尾且公差为 d 的最长子序列存在，此时则需要更新 dp\[num\] 与 res：

dp[num] = Math.max(dp[num], dp[prev] + 1);
    res = Math.max(res, dp[num]);

*  否则，将 dp\[num\] 更新为 `Math.max(dp[num], 1)`

④ 枚举完 d 后，直接返回 res 即可。

## 3.代码实现（Java） ##

//思路1————
    class Solution {
        
        public int longestArithSeqLength(int[] nums) {
        
            int n = nums.length;
            int minNum = Arrays.stream(nums).min().getAsInt();
            int maxNum = Arrays.stream(nums).max().getAsInt();
            int diff = maxNum - minNum;
            int res = 2;
            //枚举所有可能的公差
            for (int d = -diff; d <= diff; d++) {
        
                // dp[i] 表示以 nums[i] 结尾且公差为 d 的最长子序列长度
                int[] dp = new int[maxNum + 1];
                //因为以 nums[i] 结尾且公差为 d 的最长子序列不一定存在，因此先将其值初始化为 -1，方便后续进行判断
                Arrays.fill(dp, -1);
                for (int num : nums) {
        
                    int prev = num - d;
                    /*
                        prev >= minNum && prev <= maxNum: 判断边界
                        dp[prev] != -1 说明以 nums[prev] 结尾且公差为 d 的最长子序列存在
                    */
                    if (prev >= minNum && prev <= maxNum && dp[prev] != -1) {
        
                        //更新 dp[num] 与 res
                        dp[num] = Math.max(dp[num], dp[prev] + 1);
                        res = Math.max(res, dp[num]);
                    }
                    dp[num] = Math.max(dp[num], 1);
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/longest-arithmetic-subsequence/solution/zui-chang-deng-chai-shu-lie-by-leetcode-eieq8/