LIS using Segment Tree in Java
The longest increasing Sequence (LIS) problem is a classic problem in computer science and competitive programming. It involves finding the length of the longest strictly increasing subsequence. Key concepts include coordinate compression, Segment Tree structure, and query and update operations.
Example:
arr[] = {2, 1, 3}
![LIS using Segment Tree in Java](https://static.tutorialandexample.com/java/lis-using-segment-tree-in-java1.png)
![LIS using Segment Tree in Java](https://static.tutorialandexample.com/java/lis-using-segment-tree-in-java2.png)
![LIS using Segment Tree in Java](https://static.tutorialandexample.com/java/lis-using-segment-tree-in-java3.png)
![LIS using Segment Tree in Java](https://static.tutorialandexample.com/java/lis-using-segment-tree-in-java4.png)
Using Segment Tree
Algorithm
Step 1: Create a sorted copy of the input array and assign each unique value to a unique index.
Step 2: Initialize a segment tree with a size equal to the number of unique values from the coordinate compression.
Step 3: Convert each element to its compressed coordinate, query the segment tree for the maximum value in the range [0, compressed coordinate - 1], increment the maximum value by 1, update the segment tree at the compressed coordinate, and track the maximum LIS length.
Step 4: Return the resulting maximum LIS length.
Here is an implementation of finding the longest increasing subsequence using a segment tree:
FileName:LISUsingSegmentTree.java
import java.util.*; public class LISUsingSegmentTree { static class SegmentTree { int[] tree; int n; public SegmentTree(int size) { this.n = size; tree = new int[2 * n]; } // Update the segment tree at position pos with value public void update(int pos, int value) { pos += n; tree[pos] = value; for (pos /= 2; pos > 0; pos /= 2) { tree[pos] = Math.max(tree[2 * pos], tree[2 * pos + 1]); } } // Query the maximum value in the range [left, right) public int query(int left, int right) { int maxVal = 0; left += n; right += n + 1; while (left < right) { if ((left & 1) == 1) { maxVal = Math.max(maxVal, tree[left]); left++; } if ((right & 1) == 1) { right--; maxVal = Math.max(maxVal, tree[right]); } left /= 2; right /= 2; } return maxVal; } } public static int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) { return 0; } // Coordinate compression int[] sortedNums = nums.clone(); Arrays.sort(sortedNums); Mapcompress = new HashMap<>(); int index = 0; for (int num : sortedNums) { if (!compress.containsKey(num)) { compress.put(num, index++); } } // Segment Tree SegmentTree segmentTree = new SegmentTree(compress.size()); int maxLength = 0; for (int num : nums) { int compressedIndex = compress.get(num); int maxVal = segmentTree.query(0, compressedIndex - 1) + 1; segmentTree.update(compressedIndex, maxVal); maxLength = Math.max(maxLength, maxVal); } return maxLength; } public static void main(String[] args) { int[] nums = {10, 9, 2, 5, 3, 7, 101, 18}; System.out.println("Length of LIS: " + lengthOfLIS(nums)); } }
Output:
Length of LIS: 4
Complexity analysis: The time complexity of the above approach is O(n log n) due to the time complexity of sorting the array, building the compression map, and performing segment tree operations. The space complexity is O(n log n) due to the size of the segment tree array and the time complexity of the query and update operations for each element.