[BOJ] 11055 가장 큰 증가 부분 수열

문제보기

반복문을 돌면서 현재 위치(i)에서 전 번호들(j)의 수가 자신보다 작을때만 

d[i] = d[j] + a[i]

이때 가장 큰 값을 d[i]에 저장해야하므로

d[i] = max(d[i], d[j] + a[i])

---

#include <algorithm>

using namespace std;

int main(){

int N,res;

int a[1001];

int d[1001] = {};

scanf("%d",&N);

for(int i = 1;i<=N;i++){

scanf("%d",&a[i]);

d[i] = a[i];

}

res = d[1];

for(int i = 1;i<=N;i++){

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

if(a[i] > a[j]){

d[i] = max(d[i],d[j] + a[i]);

if(res < d[i]) res = d[i];

//printf("%d %d\n",i,d[i]);

}

}

}

printf("%d\n",res);

}