# 1. Introduction

The *Longest Increasing Subsequence* (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. It’s important to note that the subsequence does not need to be contiguous, but it must maintain the same relative order.

# 2. Program Steps

1. Initialize an array *lis* with the length of the given sequence and fill it with *1*s. This array will help track the length of the LIS ending at each index.

2. Iterate through the given sequence comparing elements.

3. For each pair of elements, check if increasing and update the *lis* value.

4. Return the maximum value from the *lis* array.

# 3. Code Program

```
public class LIS {
static int longestIncreasingSubsequence(int arr[], int n) {
int lis[] = new int[n];
int i, j, max = 0;
// Initialize LIS values for all indices
for (i = 0; i < n; i++)
lis[i] = 1;
// Compute LIS values in bottom up manner
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
// Return the maximum value of lis[]
for (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 };
int n = arr.length;
System.out.println("Length of the LIS is " + longestIncreasingSubsequence(arr, n));
}
}
```

### Output:

Length of the LIS is 6

# 4. Step By Step Explanation

1. The *longestIncreasingSubsequence* function calculates the length of the LIS for the given array.

2. We first initialize an array *lis* with ones. The value of *lis[i]* gives the length of the LIS ending at index *i*.

3. For each pair of indices *(i, j)*, if *arr[i] > arr[j]* (i.e., the sequence is increasing) and the LIS ending at *i* is less than the LIS ending at *j* plus 1, then we update *lis[i]*. This step effectively builds upon previously computed LIS values.

4. Finally, we return the maximum value from the *lis* array, which represents the length of the overall LIS.

5. The *main* method initializes an array, calls *longestIncreasingSubsequence*, and prints the result.