11055_가장 큰 증가 부분 수열

▶실버2

풀이

기본적으로 dp[i] = arr[i]인 상태에서 arr[j](이전 값) < arr[i](현재 기준값)을 만족할 때, dp[j] + arr[i] 와 dp[i] 중 큰 값을 선택하여 dp[i]에 대입한다. 

위의 예제를 표로 나타내면

1	100	2	50	60	3	5	6	7	8
1	101	1 + 2 = 3	max(1, 3) + 50 = 53	max(1, 3, 53) + 60 = 113	max(1, 3) + 3 = 6	max(1, 3, 6) + 5 = 11	max(1, 3, 6, 11) + 6 = 17	max(1, 3, 6, 11, 17) + 7 = 24	max(1, 3, 6, 11, 17, 24) + 8 = 32

dp값 중 가장 큰 값이 답

코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int dp[1001];
int arr[1001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = arr[i];
	}

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			ans = dp[i];
		}
		for (int j = 0; j < i; j++) {
			//증가 수열 조건 만족
			if (arr[j] < arr[i]) {
				dp[i] = max(dp[j] + arr[i], dp[i]);
			}

			//증가 수열 조건 불만족
			else continue;

		}
		ans = max(ans, dp[i]);
	}
	cout << ans;
}