up sequence 문서

이런 유형의 다이나믹 프로그래밍이 처음에는 이해가 쉽지 않습니다. 하지만 다이나믹 프로그래밍 접근 하는 방법에서 중요한 부분이니 꼭 이해하세요.

6 2 9 8 3 4 1 7 4

• 6 은 1
• 2 는 1
• 9 는 2 ( 6 9 혹은 2 9 )
• 8 은 2 ( 6 8 혹은 2 8 )
• 3 은 2 ( 2 3 )
• 4 는 3 ( 2 3 4 )
• 1 은 1

이 중 최대 길이에 7 을 붙이는게 최대. 이 경우에는 4 가 3 으로 최대이므로 7 의 최대 up sequence 의 길이는 4 가 됩니다.

다음 수 4 도 같은 방법으로 확장 합니다.

구한 up sequence 중에 최대 값이 최대 up sequence.

소스

for(i = 1;i <= 데이터의 개수 ;i++){
   max = 0;
   for(j = i-1; j >= 1;j--)
      if (data[i] > data[j]) // j 번째 데이터가 i 번째 데이터보다 작으면 
         if (max < m[j] ) max=m[j];
   up[i] = max+1;
}

//최대 up sequence 구하기 ans

ans = up[1];
for( i = 2 ; i <= 데이터의 개수;i++){
   if ( ans < up[i] ) ans = up[i];
}

분석

출처:dovelet