171209_11055_가장 큰 증가 부분 수열

//https://www.acmicpc.net/problem/11055 #include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int A[1001];

int dp[1001];

int x,max,index;

for(int i=1; i<=n; i++) cin >> A[i];

dp[1]=A[1];

for(int i=2; i<=n; i++)

{

max=0;

for(int j=i-1; j>0; j--)

{

x=A[i];

if(A[i]>A[j]) x=dp[j]+A[i];

if(max<x) { max=x;}

}

dp[i]=max;

}

max=0;

for(int i=1; i<=n; i++)

if(max<dp[i]) max=dp[i];

cout << max;

}

어제 한 상자 넣기랑 같다. 숫자, 수열로만 접근했을 때는 해결책을 못 찾아서 dp 문제를 풀면서 미뤄뒀던 문제들인데 푸는 방법을 이제 알겠음!