(알고스팟) (동적계획) 최대 증가부분 수열 구하기

정수수열 S의 부분 수열이란 S에서 0개 이상의 숫자를 지우고 남은 수열을 말한다.
예를들어, '1 2 4'는 '1 5 2 4 7'의 부분 수열이다.
{3,2,1,7,5,4,2,6}의 최대 부분 수열의 길이를 구하라

<내가 푼 방법>
private static int Lis(int A[],int index){
if(index==N)
return 1;

int max=0;
for(int i=index+1;i<N;i++){
if(A[index]<A[i])
max=Math.max(max,Lis(A,i+1)+1);
}
return max;
}

<책 내용>
private static int Lis(Vector<Integer> v){

if(v.isEmpty())return 1;
int ret=0;
for(int i=0;i<v.size();i++){
Vector<Integer> temp=new Vector<Integer>();
for(int j=i+1;j<v.size();j++){
if(v.get(i)<v.get(j))
temp.addElement(v.get(j));
ret=Math.max(ret,Lis(temp)+1);
}
}
return ret;
}

댓글

이 블로그의 인기 게시물

(ElasticSearch) 결과에서 순서 정렬

(네트워크)폴링방식 vs 롱 폴링방식

(18장) WebSocekt과 STOMP를 사용하여 메시징하기