# 1. Introduction

This blog post explores the "Longest Increasing Subsequence" problem, a common challenge in dynamic programming. The problem focuses on finding the length of the longest subsequence in an array that is strictly increasing. This is an essential concept in computer science and mathematics, particularly in the areas of algorithm design and sequence analysis.

## Problem

Given an integer array *nums*, the goal is to determine the length of the longest strictly increasing subsequence in the array.

Example scenarios:

1. For *nums = [10,9,2,5,3,7,101,18]*, the longest increasing subsequence is *[2,3,7,101]* with a length of 4.

2. For *nums = [0,1,0,3,2,3]*, the length is 4.

3. For *nums = [7,7,7,7,7,7,7]*, the length is 1, as all elements are equal.

# 2. Solution Steps

1. Use dynamic programming to construct an array *dp* where *dp[i]* represents the length of the longest increasing subsequence ending with *nums[i]*.

2. Initialize each element in *dp* to 1, as the minimum length for each element is 1.

3. Iterate through the array, for each element *nums[i]*, compare it with previous elements *nums[j]* where *j < i*.

4. If *nums[j] < nums[i]*, update *dp[i]* as *Math.max(dp[i], dp[j] + 1)*.

5. Keep track of the maximum value in the *dp* array, which represents the length of the longest increasing subsequence.

6. Return the maximum value found.

# 3. Code Program

```
public class LongestIncreasingSubsequence {
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println(lengthOfLIS(nums)); // Test the function
}
// Function 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;
}
}
```

### Output:

4

### Explanation:

1. *lengthOfLIS*: This function computes the length of the longest increasing subsequence in the array *nums*.

2. It initializes a *dp* array where *dp[i]* represents the longest increasing subsequence ending at *nums[i]*.

3. The function iterates through each element of *nums*. For each element, it compares it with all previous elements to find the longest increasing subsequence ending at that element.

4. If a smaller element is found, *dp[i]* is updated to the maximum of its current value and the length of the increasing subsequence ending at the smaller element plus one.

5. The function keeps track of and updates the maximum length found so far.

6. This approach ensures that the problem is solved optimally at each step, building up the solution for the longest increasing subsequence.

## Comments

## Post a Comment