[Java] 가장 큰 증가하는 부분 수열 [11055번]

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

• 예제 입력1

10
1 100 2 50 60 3 5 6 7 8

• 예제 출력1

113

---

• 문제 접근
  • 입력
    • 수열의 개수
    • 수열
  • 출력
    • 가장 큰 수열의 합
• 문제 해결
  • 가장 긴 감소하는 수열 문제와 크게 다르지 않음
  • dp에는 자기 자신의 숫자로 초기화
  • 현재의 인덱스가 기존의 인덱스보다 클 경우 dp[i] = dp[i]와 dp[j] + 현재값 중 큰 값
    • dp[j]에는 이미 오름차순 수열의 최댓값이 저장되어 있음

• 기존 풀이 [메모리 : 15604 KB / 시간 : 164 ms]

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int size = Integer.parseInt(br.readLine());
    int[] sequence = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    int[] dp = new int[size];

    // dp는 수열의 숫자로 초기화
    System.arraycopy(sequence, 0, dp, 0, dp.length);

    for(int i = 1; i < size; i++){
        for(int j = 0; j < i; j++){
            // j 수열의 값이 현재 수열의 값보다 작다면
            if(sequence[j] < sequence[i]){
                // 현재 오름차순 수열의 합 vs j에 있는 오름차순 수열의 합 + 현재 값 중 큰 값
                dp[i] = Math.max(dp[i], dp[j] + sequence[i]);
            }
        }
    }

    System.out.println(Arrays.stream(dp).max().getAsInt());
}