swea_d3_3307_최장증가부분수열

package algo;
import java.util.*;
import java.io.*;

public class Solution_d3_3307_최장증가부분수열 {
	public static void main(String args[]) throws Exception
	{
		System.setIn(new FileInputStream("res/input_3307.txt"));

		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int tc = 1; tc <= T; tc++)
		{
			int n = sc.nextInt();
			int[] a = new int[n];
			for(int i=0; i<n; i++) {
				a[i]= sc.nextInt();
			}
			int[] d = new int[n];
			for(int i=0; i<n; i++) {
				d[i] = 1;
				for(int j=0; j<i; j++) {
					if(a[j]<a[i]&&d[i]<d[j]+1) {
						d[i]=d[j]+1;
					}
				}
			}
			int ans = d[0];
			for(int i=0; i<n; i++) {
				if(ans<d[i]) {
					ans = d[i];
				}
			}
			System.out.println("#"+tc+" "+ans);
		}
	}
}

 

수열이 423156이라하자

1) d[0] = 1

 

2) d[1] =1

a[0]> a[1] 임으로 

d[1] =1 

 

3) d[2] =1

a[2] 가 a[1] 보다 큼으로 +1

d[2] = d[1] +1

 

4) d[3] =1

 

5) d[4] =1

a[4] 가 a[0] 보다 큼으로 

d[4] = d[0] +1 =2;

a[4] 가 a[1] 보다 큼으로 

d[4] = d[0] +1 =2;

a[4] 가 a[2] 보다 큼으로

d[4] = d[2] +1 =3;

a[4] 가 a[3] 보다 크나 원래 d[4]가 더 큼으로 생략

d[4] = 3;

 

.....

a[0]	a[1]	a[2]	a[3]	a[4]	a[5]
4	2	3	1	5	6
d[0]	d[1]	d[2]	d[3]	d[4]	d[5]
1	1	2	1	3	4