🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
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. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment