가장 큰 증가 부분 수열

https://www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

// 코드

import java.util.*;
import java.io.*;
 
class Main{    
  
  public static void main(String[] args) throws Exception {
    // Please Enter Your Code Here
    StringBuilder sb  = new StringBuilder();
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
    int n = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int myMax = Integer.MIN_VALUE;
    int[] arr = new int[n + 1];
    int[] dp  = new int[n + 1]; 
    
    for(int i=1; i<=n; ++i) {
      arr[i] = Integer.parseInt(st.nextToken());
      dp[i]  = arr[i];
    }
    
    for(int i=1; i<=n; ++i) {
      for(int j=1; j<i; ++j) {
        if(arr[i] > arr[j]) dp[i] = Math.max(arr[i] + dp[j], dp[i]);
      }
      myMax = Math.max(dp[i], myMax);
    }
    
    bw.write(String.valueOf(myMax));
    br.close();
    bw.flush();
    bw.close();
  }
}