/
NikolayIvkin
/
TheAlgorithms
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/main/java/com/thealgorithms/dynamicprogramming/LongestArithmeticSubsequence.java
42 строки
1 KB
Tejaswi Tyagi
Adds Longest Arithmetic Subsequence Implementation (#5501)
03 окт 2024, 16:04
Не верифицирован
03 окт 2024, 16:04
be8df21
Код
Авторство
О чём код?
package com.thealgorithms.dynamicprogramming; import java.util.HashMap; final class LongestArithmeticSubsequence { private LongestArithmeticSubsequence() { } /** * Returns the length of the longest arithmetic subsequence in the given array. * * A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value * (for 0 <= i < seq.length - 1). * * @param nums the input array of integers * @return the length of the longest arithmetic subsequence */ public static int getLongestArithmeticSubsequenceLength(int[] nums) { if (nums == null) { throw new IllegalArgumentException("Input array cannot be null"); } if (nums.length <= 1) { return nums.length; } HashMap<Integer, Integer>[] dp = new HashMap[nums.length]; int maxLength = 2; // fill the dp array for (int i = 0; i < nums.length; i++) { dp[i] = new HashMap<>(); for (int j = 0; j < i; j++) { final int diff = nums[i] - nums[j]; dp[i].put(diff, dp[j].getOrDefault(diff, 1) + 1); maxLength = Math.max(maxLength, dp[i].get(diff)); } } return maxLength; } }