[BOJ/11055] 가장 큰 증가 부분 수열

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

- https://www.acmicpc.net/problem/11055

 

사용 알고리즘

- DP

 

풀이

- d[i] = a[i]를 가장 마지막으로 하는 가장 큰 증가 부분 수열의 합

- d[i] = max(d[j]) + a[i] (j < i, a[j] < a[i])

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/11055.cpp

#include <cstdio>   int d[1003]; int a[1003];   int main(void) {     int n; scanf("%d", &n);     for (int i = 0; i < n; ++i) scanf("%d", &a[i]);     int ans = -1;     for (int i = 0; i < n; ++i) {         d[i] = a[i];         for (int j = 0; j < i; ++j) {             if ((a[j] < a[i]) && (d[j] + a[i] > d[i])) d[i] = d[j] + a[i];         }         if (ans < d[i]) ans = d[i];     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs