[백준] 11055-가장 큰 증가 부분 수열

전형적인 dp문제입니다.

반복문으로 arr배열을 탐색하면서 

자신보다 arr값이 작고 dp값이 가장큰 값에 자신의 arr값을 더한값이 dp값이 되는 점화식입니다. 

즉 , dp[i] = arr[i] + dp[maxed_index]의 형태가 됩니다.

전체코드입니다:)

#include <iostream>
using namespace std;

int n, result = 0;
int arr[1001] = { 0 };
int dp[1001] = { 0 };


int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) 
		cin >> arr[i];
	
	for (int i = 1; i <= n; i++) {
		int maxed = 0,maxed_index=0;
		for (int j = i - 1; j >= 1; j--) {
			if (arr[j] < arr[i] && maxed < dp[j] )
				maxed = dp[j], maxed_index = j;
		}
		dp[i] = arr[i] + dp[maxed_index];
		if (result < dp[i]) result = dp[i];
	}

	cout << result << endl;
}