【Java每日一题,动态规划】最长定差子序列

简介: 【Java每日一题,动态规划】最长定差子序列

Introduction

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


Input

第一行给出整数个数n,第二行给出n个排列整数,第三行间隔


Output

对每一组输入,在一行中输出最长等差子序列的长


Sample

input

5
1 2 3 4 5
1

output

5

Solution

import java.util.HashMap;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=s.nextInt();
        }
        int k=s.nextInt();
        int ans=0;
        HashMap<Integer,Integer> map=new HashMap();
        for(int i=0;i<n;i++){
            int num=map.getOrDefault(arr[i]-k,0);
            map.put(arr[i],num+1);
            ans=Math.max(num+1,ans);
        }
        System.out.println(ans);
    }
}

Experience

dp也能用map来实现

相关文章
|
7月前
|
Java
0-1背包问题(Java详解)(动态规划)至少与恰好
0-1背包问题(Java详解)(动态规划)至少与恰好
61 1
|
7月前
|
存储 Java 数据处理
|
7月前
|
算法 Java
[Java·算法·简单] LeetCode 392. 判断子序列 详细解读
[Java·算法·简单] LeetCode 392. 判断子序列 详细解读
85 0
|
5月前
|
Arthas 监控 算法
JVM成神路终章:深入死磕Java虚拟机序列总纲
JVM成神路终章:深入死磕Java虚拟机序列总纲
118 1
|
6月前
|
算法 Java 决策智能
Java数据结构与算法:动态规划之背包问题
Java数据结构与算法:动态规划之背包问题
|
6月前
|
算法 Java Go
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
72 0
|
7月前
|
Java Go C++
Golang每日一练(leetDay0112) 2、3、4的幂
Golang每日一练(leetDay0112) 2、3、4的幂
54 0
Golang每日一练(leetDay0112) 2、3、4的幂
|
7月前
|
Java Go C++
Golang每日一练(leetDay0085) 2的幂、数字 1 的个数
Golang每日一练(leetDay0085) 2的幂、数字 1 的个数
52 0
Golang每日一练(leetDay0085) 2的幂、数字 1 的个数
|
7月前
|
算法 Java C++
Java每日一练(20230424) 二叉树中序遍历、交换链表节点、不同子序列
Java每日一练(20230424) 二叉树中序遍历、交换链表节点、不同子序列
63 0
Java每日一练(20230424) 二叉树中序遍历、交换链表节点、不同子序列
|
7月前
|
Java Go C++
Java每日一练(20230420) 罗马数字转整数、电话号码的字母组合、排列序列
Java每日一练(20230420) 罗马数字转整数、电话号码的字母组合、排列序列
60 0
Java每日一练(20230420) 罗马数字转整数、电话号码的字母组合、排列序列