이 문제는 LIS의 기본적인 문제를 응용한 것인데, 나같은 알린이는 초기값때문에 많이 고생을 했다....
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<set>
#include<cstdlib>
#include<sstream>
using namespace std;
long long d[10001];
int a[10001];
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
d[1] = a[1];
for (int i = 1; i <= n; i++) {
//d[i] = a[i];
for (int j = 1; j <i; j++) {
if (a[j] < a[i] && d[j] + a[i]> d[i]) {
d[i] = d[j] + a[i];
}
}
}
long long maxx = -1;
for (int i = 1; i <= n; i++) {
maxx = max(maxx, d[i]);
cout << d[i] << ' ';
}
cout << maxx;
return 0;
}
여기에서 주목해야 할 것은 주석 처리한 d[i] = a[i] 인데, 초기값으로 d[i] = a[i] 를 갖고 있지않다면 다음과 같은 반례가 존재한다.
7
3 2 1 2 3 4 5
여기서 3 다음 2,1이 d[i]의 값이 0이 되어 2,3,4,5의 값이 제대로 나오지 않는다는 것을 알 수 있다.