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

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; int cookies_count; //가장 긴 증가하는 부분 수열 int eatCookie(vector<int> cookies) { int answer = 0; vector<int> DP(cookies_count + 1, 0); for (int j = 0; j < cookies_count; j++) { int Min = 0; for (int k = 0; k < j; k++) { if (cookies[j] > cookies[k]) if (Min < DP[k]) Min = DP[k]; } DP[j] = Min + 1; answer = max(DP[j], answer); } return answer; } //가장 큰 증가하는 부분 수열의 합 int Baekjoon(vector<int> cookies) { int answer = 0; vector<int> DP(cookies_count + 1, 0); for (int j = 0; j < cookies_count; j++) { int Max = 0; for (int k = 0; k < j; k++) { if (cookies[j] > cookies[k]) Max = max(Max, DP[k]); } DP[j] = Max + cookies[j]; answer = max(answer, DP[j]); } return answer; } int main() { scanf("%d", &cookies_count); vector<int > test(cookies_count, 0); for (int j = 0; j < cookies_count; j++) scanf("%d", &test[j]); cout << Baekjoon(test); return 0; }