Freestyle | Longest Increasing Subsequence (LIS) | Java

devstromo · devstromo · commit a6b25aca8ab5 · 2025-05-25T19:14:51.000-03:00
diff --git a/freestyle/src/main/java/com/devstromo/dp/lis/practice/with_k_replacement/DESCRIPTION.md b/freestyle/src/main/java/com/devstromo/dp/lis/practice/with_k_replacement/DESCRIPTION.md
@@ -0,0 +1,37 @@
+# Longest Increasing Subsequence with k Replacements
+
+## Problem Statement
+
+Given an array of integers `nums` and an integer `k`, return the length of the longest strictly increasing subsequence that can be formed by **replacing up to `k` elements** of the array with any values of your choice (not necessarily from the array).
+
+You may perform at most `k` replacements. Your goal is to **maximize** the length of the resulting strictly increasing subsequence.
+
+## Input
+
+- An integer array `nums` of length `n` where `1 <= n <= 1000`
+- An integer `k` where `0 <= k <= n`
+
+## Output
+
+- An integer representing the length of the longest strictly increasing subsequence achievable by replacing up to `k` elements.
+
+## Example
+
+### Input
+- `nums = [5, 3, 4, 2, 6]`
+- `k = 1`
+
+### Output
+
+- `4`
+
+### Explanation
+
+The standard LIS is `[3, 4, 6]` (length 3).  
+If we replace the `2` with `5`, we can obtain `[3, 4, 5, 6]` — strictly increasing, length 4.
+
+## Constraints
+
+- `1 <= nums.length <= 1000`
+- `-10^9 <= nums[i] <= 10^9`
+- `0 <= k <= nums.length`
diff --git a/freestyle/src/main/java/com/devstromo/dp/lis/practice/with_k_replacement/Solution.java b/freestyle/src/main/java/com/devstromo/dp/lis/practice/with_k_replacement/Solution.java
@@ -0,0 +1,33 @@
+package com.devstromo.dp.lis.practice.with_k_replacement;
+
+import java.util.Arrays;
+
+public class Solution {
+    public int longestIncreasingSubsequenceWithKReplacements(int[] nums, int k) {
+        int n = nums.length;
+        int[][] dp = new int[n + 1][k + 1];
+
+        // Initialize to 1 since the minimum LIS at any position is 1
+        for (int[] row : dp) Arrays.fill(row, 1);
+
+        int maxLen = 1;
+
+        for (int i = 1; i < n; i++) {
+            for (int r = 0; r <= k; r++) {
+                for (int j = 0; j < i; j++) {
+                    for (int prevRepl = 0; prevRepl <= r; prevRepl++) {
+                        if (nums[j] < nums[i]) {
+                            dp[i][r] = Math.max(dp[i][r], dp[j][prevRepl] + 1);
+                        } else if (r > 0) {
+                            // Try replacing nums[i] to be greater than nums[j]
+                            dp[i][r] = Math.max(dp[i][r], dp[j][r - 1] + 1);
+                        }
+                    }
+                }
+                maxLen = Math.max(maxLen, dp[i][r]);
+            }
+        }
+
+        return maxLen;
+    }
+}
diff --git a/freestyle/src/test/java/com/devstromo/dp/lis/practice/with_k_replacement/SolutionUnitTest.java b/freestyle/src/test/java/com/devstromo/dp/lis/practice/with_k_replacement/SolutionUnitTest.java
@@ -0,0 +1,50 @@
+package com.devstromo.dp.lis.practice.with_k_replacement;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SolutionUnitTest {
+    private final Solution solution = new Solution();
+
+    @Test
+    @DisplayName("Test Longest Increasing Subsequence with k Replacements")
+    void testLongestIncreasingSubsequenceWithKReplacements() {
+        int[] nums = {5, 3, 4, 2, 6};
+        int k = 1;
+        assertEquals(4, solution.longestIncreasingSubsequenceWithKReplacements(nums, k));
+    }
+
+    @Test
+    @DisplayName("Test No Replacement Needed")
+    void testNoReplacementNeeded() {
+        int[] nums = {1, 2, 3, 4, 5};
+        int k = 0;
+        assertEquals(5, solution.longestIncreasingSubsequenceWithKReplacements(nums, k));
+    }
+
+    @Test
+    @DisplayName("Test One Replacement To Start")
+    void testOneReplacementToStart() {
+        int[] nums = {5, 1, 2, 3, 4};
+        int k = 1;
+        assertEquals(5, solution.longestIncreasingSubsequenceWithKReplacements(nums, k));
+    }
+
+    @Test
+    @DisplayName("Test Max Replacements")
+    void testMaxReplacements() {
+        int[] nums = {9, 8, 7, 6, 5};
+        int k = 4;
+        assertEquals(5, solution.longestIncreasingSubsequenceWithKReplacements(nums, k));
+    }
+
+    @Test
+    @DisplayName("Test Zero LIS")
+    void testZeroLIS() {
+        int[] nums = {5, 5, 5, 5};
+        int k = 0;
+        assertEquals(1, solution.longestIncreasingSubsequenceWithKReplacements(nums, k));
+    }
+}
