# 1. Introduction

The Longest Increasing Subsequence (LIS) problem is a well-known challenge in the algorithms domain. Given a sequence of numbers, the goal is to find the length of the longest subsequence that is strictly increasing. A subsequence is derived from the original sequence by deleting some elements, possibly none, without changing the order of the remaining elements. The problem has an efficient solution using dynamic programming.

# 2. Program Steps

1. Initialize an array *lis* of size *n* (length of the given sequence) where each element is set to 1. This array will store the LIS ending at each index.

2. Using a nested loop, compare elements of the sequence and update the *lis* array based on previous computations.

3. Return the maximum value in the *lis* array, which represents the length of the LIS.

4. In the *main* method, input an example sequence and compute its LIS.

# 3. Code Program

```
class LongestIncreasingSubsequence {
public static int lis(int[] arr) {
int n = arr.length;
int[] lis = new int[n];
int max = 0;
for (int i = 0; i < n; i++) {
lis[i] = 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;
}
}
}
for (int i = 0; i < n; i++) {
if (max < lis[i]) {
max = lis[i];
}
}
return max;
}
public static void main(String[] args) {
int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
System.out.println("Length of LIS is: " + lis(arr));
}
}
x
```

### Output:

Length of LIS is: 6

# 4. Step By Step Explanation

1. The method *lis* calculates the longest increasing subsequence of a given sequence.

2. We first initialize the *lis* array with all values set to 1 because a single element is an increasing sequence of length 1.

3. Using nested loops, for every element *arr[i]*, we compare it with all elements before it. If *arr[i]* is greater than a previous element *arr[j]* and the length of LIS ending at *arr[i]* is less than the length of LIS ending at *arr[j]* plus one, then update *lis[i]*.

4. After constructing the *lis* array, we extract the maximum value, which gives us the length of the longest increasing subsequence.

5. The *main* method offers a sample sequence. The longest increasing subsequence for this sequence is: 10, 22, 33, 50, 60, 80, hence the length 6.