# 1. Introduction

In this blog post, we will explore a classic problem in dynamic programming - finding the Longest Increasing Subsequence (LIS) in an array of integers. The LIS is a subsequence of a given sequence in which the elements are in sorted order, lowest to highest, and in which the sequence is as long as possible.

## Problem

Given an array of integers A, find the length of the longest strictly increasing subsequence of A. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

# 2. Solution Steps

1. Initialize an array dp of the same length as A, where each element is 1. dp[i] represents the length of the longest increasing subsequence ending with A[i].

2. Iterate over the array A starting from the second element.

3. For each element A[i], iterate over all previous elements A[j] where j < i.

4. If A[j] < A[i], update dp[i] to be the maximum of dp[i] and dp[j] + 1.

5. The length of the longest increasing subsequence will be the maximum value in dp.

6. Return the maximum value in dp.

# 3. Code Program

``````public class Solution {

// Main method for testing
public static void main(String[] args) {
int[] nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("Length of LIS: " + lengthOfLIS(nums1));

int[] nums2 = {0, 1, 0, 3, 2, 3};
System.out.println("Length of LIS: " + lengthOfLIS(nums2));

int[] nums3 = {7, 7, 7, 7, 7, 7, 7};
System.out.println("Length of LIS: " + lengthOfLIS(nums3));
}

// Method to find the length of the longest increasing subsequence
public static int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;

int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxLen = 1;

for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}

return maxLen; // The length of the longest increasing subsequence
}
}
``````

### Output:

```Length of LIS: 4
Length of LIS: 4
Length of LIS: 1
```

### Explanation:

For the first example, the longest increasing subsequence is [2,3,7,101], so the length is 4. The method lengthOfLIS uses dynamic programming to build up a solution. It iterates through each element and calculates the length of the longest increasing subsequence ending at that element. The final answer is the maximum length found in the array.

# My Top and Bestseller Udemy Courses

Check out all my Udemy courses and updates:
Udemy Courses - Ramesh Fadatare