DP #07. Longest Increasing Subsequence. - mbhushan/dynpro GitHub Wiki

(7). Longest Increasing Subsequence.

Find the longest increasing subsequence in an array.

Input:
int [] A = {3, 4, -1, 0, 6, 2, 3}

Output:
LIS: 4 (-1, 0, 2, 3)


Formula:
if (A[j] < A[i]) {
   T[i] = Max (T[i], T[j] + 1);
}

Time complexity: O(n^2)
Space complexity: O(n)


                int [] T = new int[A.length];
		for (int i=0; i<T.length; i++) {
			T[i] = 1;
		}
		
		for (int i=1; i<A.length; i++) {
			for (int j=0; j<i; j++) {
				if (A[j] < A[i]) {
					T[i] = Math.max(T[i], T[j] + 1);
				}
			}
		}

Input	3	4	-1	0	6	2	3
LIS - iteration0	1	1	1	1	1	1	1
LIS - iteration1	1	2	1	1	2	1	1	j=0	i=len(A)
LIS - iteration2	1	2	1	1	3	1	1	j=1	i=len(A)
LIS - iteration3	1	2	1	2	3	2	2	j=2	i=len(A)
LIS - iteration4	1	2	1	2	3	3	3	j=3	i=len(A)
LIS - iteration5	1	2	1	2	3	3	3	j=4	i=len(A)
LIS - iteration6	1	2	1	2	3	3	4	j=5	i=len(A)
Index	0	1	2	3	4	5	6
Parent-Iteration0	-1	-1	-1	-1	-1	-1	-1
Parent-Iteration1	-1	0	-1	-1	0	-1	-1
Parent-Iteration2	-1	0	-1	-1	1	-1	-1
Parent-Iteration3	-1	0	-1	2	1	2	2
Parent-Iteration4	-1	0	-1	2	1	3	3
Parent-Iteration5	-1	0	-1	2	1	3	3
Final LIS	4

Longest increasing subsequence