Dynamic Programming 16

Given an array of integers, find the length of the longest (strictly) increasing subsequence from the given array.

Problem link :- click here

Code

import java.util.Arrays;
import java.util.Scanner;

public class DynamicProgramming_16
{
	//Recursion
	static int longestIncreasingSubsequence(int[] arr, int index, int last_num)
	{
		if(index >= arr.length)
			return 0;
		
		int with = 0, with_out = 0;
		
		if(arr[index] > last_num)
			with = 1 + longestIncreasingSubsequence(arr, index+1, arr[index]);
		with_out = longestIncreasingSubsequence(arr, index+1, last_num);
		
		return Math.max(with, with_out);
	}
	
	//DP
	//Here we have store value w.r.t index and last_num
	static int longestIncreasingSubsequence1(int[] arr)
	{
		int n = arr.length;
		int dp[] = new int[n];
		
		Arrays.fill(dp, 1);
		
		int max = 0;
		for(int i=1; i<n; i++)
			for(int j=0; j<i; j++)
				if(arr[j] < arr[i])
				{
					int len = 1 + dp[j];
					
					if(len > dp[i])
						dp[i] = len;
					
					if(len > max)
						max = len;
				}
		
		for(int x: dp)
			System.out.print(x + " ");
		
		return max;
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the size of the array : ");
		int n = s.nextInt();
		int[] arr = new int[n];
		
		System.out.println("Enter the array elements : ");
		for(int i=0; i<n; i++)
			arr[i] = s.nextInt();
		
//		int ans = longestIncreasingSubsequence(arr, 0, -1);
		int ans = longestIncreasingSubsequence1(arr);
		System.out.println("\n\n" + ans);
		
		s.close();
	}

}