Blogs Hub

by AskGif | Jul 12, 2018 | Category :coding

Find Longest Increasing Subsequence

<p>Finding Longest Increasing Subsequence in an array in N^2 Time complexity.</p> <p><span style="color: #576871; font-family: OpenSans, Arial, Helvetica, sans-serif;">The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in strictly ascending order. This is called the Longest Increasing Subsequence (LIS) problem.</span></p> <pre class="language-java"><code>public class LongestIncreasingSubsequence { private static int Max(int a, int b) { return a&gt;b?a:b; } public static void main(String[] args) { int[] arr = new int[] {5, 2, 7, 4, 3, 8}; //Array to store the result int[] resArr = new int[arr.length]; //Initialize every element of resArr to 1 for(int i=0;i&lt;arr.length;i++) { resArr[i]=1; } //Calculate each element value for resArr for(int i=0;i&lt;arr.length-1;i++) { for(int j=1;j&lt;arr.length;j++) { if(arr[i]&lt;arr[j]) { resArr[j] = Max(resArr[j],resArr[i]+1); } } } //Find the maximum element in resArr Array int max = 0; for(int i=0;i&lt;arr.length;i++) { if(resArr[i]&gt;max) max = resArr[i]; } //Print the result System.out.println(max); } } </code></pre>