728x90
https://www.acmicpc.net/problem/11722
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
// 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
|
import java.util.*;import java.io.*;
interface Main{ static void main(String[]r)throws Exception{
// Please Enter Your Code Here
int max=Integer.MIN_VALUE;
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N =Integer.parseInt(br.readLine());StringTokenizer st=new StringTokenizer(br.readLine());int[]a=new int[N],d=new int[N];
for(int i=0;i<N;++i){
d[i]=1;a[i]=Integer.parseInt(st.nextToken());
for(int j=0; j<i; ++j) if(a[j]>a[i])d[i]=Math.max(d[i], d[j]+1);
max = Math.max(max, d[i]);}
bw.write(String.valueOf(max));bw.flush();bw.close();br.close();}}
|
cs |
// 코드
|
1
|
import java.util.*;import java.io.*;interface Main{static void main(String[]r)throws Exception{int max=Integer.MIN_VALUE;BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));BufferedReader br=new BufferedReader(new InputStreamReader(System.in));int N=Integer.parseInt(br.readLine());StringTokenizer st=new StringTokenizer(br.readLine());int[]a=new int[N],d=new int[N];for(int i=0;i<N;++i){d[i]=1;a[i]=Integer.parseInt(st.nextToken());for(int j=0;j<i;++j)if(a[j]>a[i])d[i]=Math.max(d[i], d[j]+1);max=Math.max(max,d[i]);}bw.write(String.valueOf(max));bw.flush();bw.close();br.close();}}
|
cs |
반응형
'CS > 알고리즘_문제풀이(자바)' 카테고리의 다른 글
| 연속합 (0) | 2021.10.20 |
|---|---|
| 가장 긴 바이토닉 부분 수열 (0) | 2021.10.20 |
| 가장 큰 증가 부분 수열 (0) | 2021.10.19 |
| 가장 긴 증가하는 부분 수열 4 (0) | 2021.10.19 |
| 집합(비트마스크) (0) | 2021.10.19 |