WikiGalaxy
Longest Increasing Subsequence
Example 1: Basic Sequence
Description:
Given a sequence of numbers, the goal is to find the length of the longest increasing subsequence (LIS).
Example:
Input: [10, 22, 9, 33, 21, 50, 41, 60, 80]
Output: 6 (The LIS is [10, 22, 33, 50, 60, 80])
import java.util.*;
class LISExample {
static int lis(int arr[], int n) {
int lis[] = new int[n];
Arrays.fill(lis, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
return Arrays.stream(lis).max().getAsInt();
}
public static void main(String args[]) {
int arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
int n = arr.length;
System.out.println("Length of LIS is " + lis(arr, n));
}
}
Console Output:
Length of LIS is 6
Example 2: All Elements Same
Description:
When all elements in the array are the same, the LIS is 1.
Example:
Input: [5, 5, 5, 5, 5]
Output: 1 (The LIS is [5])
import java.util.*;
class LISExample {
static int lis(int arr[], int n) {
int lis[] = new int[n];
Arrays.fill(lis, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
return Arrays.stream(lis).max().getAsInt();
}
public static void main(String args[]) {
int arr[] = {5, 5, 5, 5, 5};
int n = arr.length;
System.out.println("Length of LIS is " + lis(arr, n));
}
}
Console Output:
Length of LIS is 1
Example 3: Decreasing Sequence
Description:
In a completely decreasing sequence, the LIS is always 1.
Example:
Input: [9, 7, 5, 3, 1]
Output: 1 (The LIS is [9] or [7] or any single element)
import java.util.*;
class LISExample {
static int lis(int arr[], int n) {
int lis[] = new int[n];
Arrays.fill(lis, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
return Arrays.stream(lis).max().getAsInt();
}
public static void main(String args[]) {
int arr[] = {9, 7, 5, 3, 1};
int n = arr.length;
System.out.println("Length of LIS is " + lis(arr, n));
}
}
Console Output:
Length of LIS is 1
Example 4: Random Sequence
Description:
With a random sequence, the LIS can vary significantly.
Example:
Input: [3, 10, 2, 1, 20]
Output: 3 (The LIS is [3, 10, 20])
import java.util.*;
class LISExample {
static int lis(int arr[], int n) {
int lis[] = new int[n];
Arrays.fill(lis, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
return Arrays.stream(lis).max().getAsInt();
}
public static void main(String args[]) {
int arr[] = {3, 10, 2, 1, 20};
int n = arr.length;
System.out.println("Length of LIS is " + lis(arr, n));
}
}
Console Output:
Length of LIS is 3
Example 5: Mixed Sequence
Description:
A sequence with both increasing and decreasing elements can have multiple valid LIS.
Example:
Input: [0, 8, 4, 12, 2]
Output: 3 (The LIS could be [0, 4, 12] or [0, 8, 12])
import java.util.*;
class LISExample {
static int lis(int arr[], int n) {
int lis[] = new int[n];
Arrays.fill(lis, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
return Arrays.stream(lis).max().getAsInt();
}
public static void main(String args[]) {
int arr[] = {0, 8, 4, 12, 2};
int n = arr.length;
System.out.println("Length of LIS is " + lis(arr, n));
}
}
Console Output:
Length of LIS is 3
