[Silver 2] 11055번 가장 큰 증가 부분 수열

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] a = br.readLine().split(" ");
        int[] k = new int[n];
        int ans = 0;
        
        for(int i=0; i<n; i++) {
            k[i] = Integer.parseInt(a[i]);
            for(int j=0; j<i; j++) {
                if(Integer.parseInt(a[j])<Integer.parseInt(a[i])) {
                    k[i] = Math.max(k[i], k[j]+Integer.parseInt(a[i]));
                }
            }
        }
        
        for(int i=0; i<n; i++) {
            if(ans<k[i]) { ans = k[i]; }
        }
        
        System.out.println(ans);
    }
}