TheAlgorithms · vil02 · Oct 3, 2024 · Oct 1, 2024 · Oct 1, 2024 · Oct 2, 2024
@@ -0,0 +1,42 @@
+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;
+    }
+}
@@ -0,0 +1,35 @@
+package com.thealgorithms.dynamicprogramming;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.util.stream.Stream;
+import org.apache.commons.lang3.ArrayUtils;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+public class LongestArithmeticSubsequenceTest {
+    @ParameterizedTest
+    @MethodSource("provideTestCases")
+    void testGetLongestArithmeticSubsequenceLength(int[] nums, int expected) {
+        assertEquals(expected, LongestArithmeticSubsequence.getLongestArithmeticSubsequenceLength(nums));
+    }
+    @ParameterizedTest
+    @MethodSource("provideTestCases")
+    void testGetLongestArithmeticSubsequenceLengthReversedInput(int[] nums, int expected) {
+        ArrayUtils.reverse(nums);
+        assertEquals(expected, LongestArithmeticSubsequence.getLongestArithmeticSubsequenceLength(nums));
+    }
+
+    @Test
+    void testGetLongestArithmeticSubsequenceLengthThrowsForNullInput() {
+        assertThrows(IllegalArgumentException.class, () -> LongestArithmeticSubsequence.getLongestArithmeticSubsequenceLength(null));
+    }
+
+    private static Stream<Arguments> provideTestCases() {
+        return Stream.of(Arguments.of(new int[] {3, 6, 9, 12, 15}, 5), Arguments.of(new int[] {1, 7, 10, 13, 14, 19}, 4), Arguments.of(new int[] {1, 2, 3, 4}, 4), Arguments.of(new int[] {}, 0), Arguments.of(new int[] {10}, 1), Arguments.of(new int[] {9, 4, 7, 2, 10}, 3),
+            Arguments.of(new int[] {1, 2, 2, 2, 2, 5}, 4));
+    }
+}