SWEA_D3_3307
π [D3_3307] μ΅μ₯ μ¦κ° λΆλΆ μμ΄
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static StringTokenizer st;
static int[] arr;
static int[] dp;
static int min, N;
static int idx;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int tc=1; tc<=T; tc++) {
sb.append("#").append(tc).append(" ");
// μμ΄μ κΈΈμ΄
N = Integer.parseInt(br.readLine());
// μ«μ λ°°μ΄
arr = new int[N];
// dp κ° μ μ₯ λ°°μ΄
dp = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// μ΄κΈ°κ° μ€μ
dp[0] = arr[0];
idx = 0;
LIS();
sb.append(idx+1).append("\n");
}
System.out.println(sb);
}
// LIS
static void LIS() {
for(int i=1; i<N; i++) {
// arr κ°μ΄ λ ν° κ²½μ°
if(arr[i] > dp[idx]) {
idx++;
dp[idx] = arr[i];
}
// dp κ°μ΄ λ ν° κ²½μ°
else {
int low = bs(idx, arr[i]);
dp[low] = arr[i];
}
}
}
// μ΄μ§ νμ
static int bs(int end, int n) {
int start = 0;
while(start < end) {
int mid = ( start + end ) / 2;
if(dp[mid] >= n) {
end = mid;
}
else {
start = mid+1;
}
}
return end;
}
}
π€ λμ μκ°
μ΄ λ¬Έμ λ LISμ μ νμ μΈ λ¬Έμ μ΄λ€.
λλ dpμ μ΄μ§ νμμ ν΅ν΄ λ¬Έμ λ₯Ό ν΄κ²°νμλ€.
LIS μ€λͺ