[11055] 가장 큰 증가하는 부분 수열

이 문제는 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의 값이 제대로 나오지 않는다는 것을 알 수 있다.