[백준/11055] 가장 긴 증가 부분 수열 (Java/코드)

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

가장 큰 증가 부분 수열 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	10522	4782	3869	46.806%

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력 1 

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1 

113

---

가장 긴 증가하는 수열과 동일한 방식이다!

다만 다른점은 증가하는 수열은 길이가 가장 긴것을 측정했다면, 이것은 연속된 합계가 가장 큰것을 더하는 것이다.

두가지 체크할 사항이 있는데,

나는 초기화 하는 과정을 놓쳤다.

d[i]=a[i] 로 잡아주어야 하는데, d[i]=1로 잡아서 백준저지 코드에서 계속 인식을 못하고 실패하고 말았다ㅠ

어차피 0부터 시작하기 때문에 상관 없을거라고 판단을 한게 미스였다.

import java.util.*;
public class Main{
 
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max=0;
        int[] d = new int[1001];
        int[] a = new int[1001];
 
        for(int i=0; i<n; i++){
            a[i]=sc.nextInt();
            d[i]=a[i];
        }
    
        for(int i=0; i<n ; i++){
            for(int j=0 ; j<=i ; j++){
                if(a[j]<a[i] && d[j]+a[i]>d[i]){
                    d[i]=d[j]+a[i];
                }
            }
        }
        
        for(int i=0; i<n ; i++){
            if(d[i]>max)
                max=d[i];
        }
 
        System.out.println( max );
        
    }  
}