[백준] C++ 11055(가장 큰 증가하는 부분 수열)

#include <iostream>

using namespace std;

int arr[1001];
int DP[1001];

int main(void)
{
	int A=0;
	
	cin>>A;
	
	for(int i=0; i<A; i++)
	{
		cin>>arr[i];
		DP[i]=arr[i];
	}
	
	int max=DP[0];
	
	for(int i=0; i<A; i++)
	{
		for(int j=0; j<i; j++)
		{
			if(arr[i]>arr[j]&&DP[i]<DP[j]+arr[i])
			{
				DP[i]=DP[j]+arr[i];
			}
			if(DP[i]>max)
			{
				max=DP[i];
			}
		}
	}
	
	cout<<max;
}

 

DP 배열에 지금까지 가능한 합을 저장한다.

만약 arr[i]가 arr[j]보다 크다면  DP[i]와DP[j]+arr[i]를 비교한 후 DP[j]+arr[i]가 더 크다면 DP[i]값을 갱신.

 

max의 초기값은 DP[0]임에 주의하자.(왜?? for문 안에서 DP[0]에 대해 검사 안 함.)