Finding the longest increasing subsequence.
Here’s a Java program that finds the longest increasing subsequence of a given array:
import java.util.Arrays;
public class LongestIncreasingSubsequence {
public static int[] findLongestIncreasingSubsequence(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int[] parent = new int[n];
Arrays.fill(parent, -1);
int lisIndex = 0;
for (int i = 1; i < n; i++) {
if (nums[i] < nums[lisIndex]) {
lisIndex = i;
} else if (nums[i] > nums[lisIndex]) {
int pos = binarySearch(nums, dp, 0, lisIndex, nums[i]);
dp[pos] = i;
parent[i] = dp[pos - 1];
lisIndex = Math.max(lisIndex, pos);
}
}
int[] lis = new int[lisIndex + 1];
int p = dp[lisIndex];
for (int i = lisIndex; i >= 0; i--) {
lis[i] = nums[p];
p = parent[p];
}
return lis;
}
private static int binarySearch(int[] nums, int[] dp, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[dp[mid]] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
public static void main(String[] args) {
int[] nums = {3, 10, 2, 1, 20};
int[] lis = findLongestIncreasingSubsequence(nums);
System.out.println("Longest Increasing Subsequence: " + Arrays.toString(lis));
}
}
This program uses the dynamic programming approach to find the longest increasing subsequence. It maintains an array `dp` to store the indexes of elements in the current longest increasing subsequence found so far. It also keeps track of the parent index of each element to reconstruct the subsequence at the end.
The `binarySearch` method is used to find the correct position to insert a new element in the `dp` array. This helps maintain the increasing order of elements in the subsequence.
In the `main` method, you can modify the `nums` array to test with different inputs. The program will output the longest increasing subsequence for the given array. In this example, the output will be `[2, 10, 20]`.
Please note that this program assumes that the input array contains only positive integers.