LIS - Longest Increasing Subsequence - Dynamic Programming

https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence/0

	/*package whatever //do not write package name here */
	import java.util.*;
	import java.lang.*;
	import java.io.*;
	class GFG {
	public static void main(String[] args) {
	//code
	Scanner scanner = new Scanner(System.in);
	int T = scanner.nextInt();
	for (int t = 0; t < T; t++) {
	int N = scanner.nextInt();
	if (N < 1) {
	System.out.println(0);
	continue;
	}
	int[] A = new int[N];
	for (int i = 0; i < N; i++) {
	A[i] = scanner.nextInt();
	}
	// DP
	int[] dp = new int[N];
	dp[0] = 1;
	int globalMax = 1;
	for (int i = 1; i < N; i++) {
	dp[i] = 1;
	int max = 0;
	for (int j = 0; j < i; j++) {
	if (A[j] < A[i]) {
	max = Math.max(max, dp[j]);
	}
	}
	dp[i] += max;
	globalMax = Math.max(globalMax, dp[i]);
	}
	// System.out.println(Arrays.toString(dp));
	System.out.println(globalMax);
	}
	}
	}

view raw LIS - Longest Increasing Subsequence - Dynamic Programming.java hosted with ❤ by GitHub