수열의 크기 N이 주어지고, 해당 수열이 주어질 때, 합이 가장 큰 증가 부분 수열의 합을 출력하는 문제
예제를 생각하면서 풀이과정을 생각해보자.
1 100 2 50 60 3 5 6 7 8
1
1 + 100
vs 1
1 + 100
vs 1 + 2
1 + 100
vs 1 + 2 + 50
…
1 + 100 vs 1 + 2 + 50 + 60
vs 1 + 2 + 3 + 5 + 6 + 7 + 8
흠 .. 각 인덱스마다 크기비교를 해주면서 그 앞에 값들도 저장을 해줘야 할 것 같다 .. 어떻게 해야할까 ?
#include <iostream>
#include <algorithm>
using namespace std;
int N, ans;
int A[1001], dp[1001];
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 0; i < N; i++) {
dp[i] = A[i];
for (int j = i; j >= 0; j--) {
if (A[i] > A[j]) {
dp[i] = max(dp[i], A[i] + dp[j]);
}
}
ans = max(ans, dp[i]);
}
cout << ans;
return 0;
}