SWEA 3307 최장 증가 부분 수열

1 개요

SWEA 3307 최장 증가 부분 수열

SW Expert 아카데미

#	문제	풀이

3 Java

import java.io.*;
import java.util.*;
public class Solution {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = sc.nextInt();
		int[] values, counts;
		int i, j, value, count, maxCount;
		for(int tc=1; tc<=T; tc++) {
			int N = sc.nextInt();
			values = new int[N];
			counts = new int[N];
			maxCount = 0;
			for(i=0; i<N; i++) {
				values[i] = sc.nextInt();
			}
			for(i=0; i<N; i++) {
				value = values[i];
				count = counts[i];
				for(j=i+1; j<N; j++) {
					if( value > values[j] ) continue;
					if( count+1 <= counts[j] ) continue;
					counts[j] = count+1;
					if( count+1 > maxCount ) maxCount = count+1;
				}
			}
			bw.append(String.format("#%d %d\n",tc, maxCount+1));
		}
		bw.flush();
		sc.close();
	}
}

4 같이 보기

• 최장 증가 부분수열