문제

문제 링크

문제 접근

  • 첫 수부터 돌면서 하나씩 값을 찾아준다.
  • 값은 이때 각 수의 위치에서 뒤로 돌면서 현재 수보다 작은 애들의 sum 값이 큰 작은 애를 찾아서 현재 수와 더해서 넣어준다.

코드

#include <cstdio>

int n, a[1001], sum[1001], MAX;
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)scanf("%d", &a[i]);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            if(a[i] <= a[j])continue;
            if(sum[i] < sum[j])sum[i] = sum[j];
        }
        sum[i] += a[i];
        if(sum[i] > MAX) MAX = sum[i];
    }
    printf("%d", MAX);
}

느낀점

  • 디피 굳!!