【Leetcode】最长定差子序列——动态规划

给你一个整数数组 arr 和一个整数 difference,请你找出并返回 arr 中最长等差子序列的长度,该子序列中相邻元素之间的差等于difference 。

子序列是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

示例 1:

输入:arr = [1,2,3,4], difference = 1
输出:4
解释:最长的等差子序列是 [1,2,3,4]。

示例 2:

输入:arr = [1,3,5,7], difference = 1
输出:1
解释:最长的等差子序列是任意单个元素。

示例 3:

输入:arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出:4
解释:最长的等差子序列是 [7,5,3,1]。

提示:

1 <= arr.length <= 105
-104 <= arr[i], difference <= 104

今天这个题比较简单的,这里用到了动态规划,其实动态规划最核心的思想,就在于拆分子问题,记住过往,减少重复计算

如果你对动态规划一无所知或者有些不熟那你可以去—>动态递归详解.

看一下这个题的代码:

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int ans = 0;
        int[] dp = new int[40001];
        for (int num : arr) {
        //因为difference+arr的最小值为-20000
        //数组下标不可以为负,所以都加20000
            dp[num + 20000] = dp[num + 20000 - difference] + 1; 
            //返回一个大的数
            ans = Math.max(ans, dp[num + 20000]);
        }
        return ans;
    }
}

如果你看不懂,那我们来举一个例子看看:

假设输入为[4,5,6,1,3,8]和2

首先遍历4,4-2=2,dp[4+20000]=dp[4+20000-2]+1;
此时dp[4+20000-2]=0,所以dp[4+20000]=1

然后遍历5,5-2=3,dp[5+20000]=dp[5+20000-2]+1
此时dp[5+20000-2]=0,所以dp[5+20000]=1

然后遍历6,6-2=4,dp[6+20000]=dp[6+20000-2]+1
此时dp[6+20000-2]=dp[4+20000]=1,所以dp[6+20000]=2

然后遍历1,1-2=-1,dp[1+20000]=dp[1+20000-2]+1
此时dp[1+20000-2]=0,所以dp[1+20000]=1

然后遍历3,3-2=1,dp[3+20000]=dp[3+20000-2]+1
此时dp[3+20000-2]=dp[1+20000]=1,所以dp[3+20000]=2

然后遍历8,8-2=6,dp[8+20000]=dp[8+20000-2]+1
此时dp[8+20000-2]=dp[6+20000]=2,所以dp[7+20000]=3

最后输出为:3

这下你应该懂了吧!很奇妙,不过这个前提是找子序列,也就是不改变元素顺序情况下!大家用之前一定要仔细读题,不要想当然哦,你现在再回头去看看代码,应该没问题吧!

最后我们在以一个例子结尾,可以先想想答案是多少,然后在看过程

输入为[4,5,6,1,3,7]和2

首先遍历4,4-2=2,dp[4+20000]=dp[4+20000-2]+1;
此时dp[4+20000-2]=0,所以dp[4+20000]=1

然后遍历5,5-2=3,dp[5+20000]=dp[5+20000-2]+1
此时dp[5+20000-2]=0,所以dp[5+20000]=1

然后遍历6,6-2=4,dp[6+20000]=dp[6+20000-2]+1
此时dp[6+20000-2]=dp[4+20000]=1,所以dp[6+20000]=2

然后遍历1,1-2=-1,dp[1+20000]=dp[1+20000-2]+1
此时dp[1+20000-2]=0,所以dp[1+20000]=1

然后遍历3,3-2=1,dp[3+20000]=dp[3+20000-2]+1
此时dp[3+20000-2]=dp[1+20000]=1,所以dp[3+20000]=2

然后遍历7,7-2=5,dp[7+20000]=dp[7+20000-2]+1
此时dp[7+20000-2]=dp[5+20000]=1,所以dp[7+20000]=2

输出为:2

欢迎大佬指点
持续更新中…

上一篇:DRF03_Serializer序列化器


下一篇:2、补充介绍