코드 복사/붙여넣기 하는 당신이 아름답습니다.

11055 : 가장 큰 증가 부분 수열

풀이

d[i] = i번째 수까지의 부분 수열 중 최댓값으로 놓자!

d[i] = d[j] + a[i]

lis에서 dp 배열에 길이를 넣는 것 대신 최댓값을 넣어주면 된다.

코드

#include <stdio.h>

int n, ans, a[1001], d[1001];

int main() {
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		d[i] = a[i];
		for (int j = 0; j <= i; j++) {
			if (a[j] < a[i] && d[i] < d[j] + a[i])
				d[i] = d[j] + a[i];
		}
		ans = ans > d[i] ? ans : d[i];
	}

	printf("%d", ans);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-08-07 16:50

Read more posts by this author