kingsubin

import java.io.*;
import java.util.StringTokenizer;

public class boj_11055 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] dp;
    static int[] val;
    static int n, ans;

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        dp = new int[n+1];
        val = new int[n+1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            val[i] = Integer.parseInt(st.nextToken());
            dp[i] = val[i];
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
              if (val[j] < val[i] && dp[i] < dp[j] + val[i]) {
                  dp[i] = dp[j] + val[i];
              }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            if (ans < dp[i]) ans = dp[i];
        }
        
        System.out.println(ans);
    }
}

 

- dp[n] -> val[n]을 마지막으로 하는 가장 큰 증가하는 부분수열의 합

- dp의 초기값을 val로 저장

- 인덱스가 나보다 작고, 값도 나보다 작은 값에 대하여 그 전까지의 합 : dp[j] + 현재 나의 값 : val[i] 을 

  구하고 그 중에 최댓값을 dp에 저장

- dp 배열중에서 가장 큰 값 출력