0x10 - DP : BOJ11055 가장 큰 증가하는 부분 수열

진짜 열받게 많이 틀림;;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] list = new int[n+1];
        for (int i = 0; i < n; i++)  list[i] = Integer.parseInt(st.nextToken());

        //1. 테이블 정의
        //d[i] : list[i] 탐색할 때의 최댓값
        int[] d = new int[n+1];

        //2. 초기값 설정
        d[0] = list[0];
        int max = d[0];

        //3. 점화식
        for (int i = 1; i < n; i++) {
            int max_i = list[i];
            int k=i-1;
            while(k>=0) {
                if(list[k]<list[i]) max_i = Math.max(max_i, d[k] + list[i]);
                k--;
            }
            d[i] = max_i;
            max = Math.max(d[i], max);
        }
        System.out.println(max);
    }
}

분명히 다른 예제들이 다 맞는데 아무리 고쳐봐도 1%에서 바로 틀린다면.... 같은 수가 여러 개인 경우가 반례일 수 있다

문제를 제대로 안 읽어서 같은 수가 여러개인 경우에도 증가하는 것으로 생각해서 다 더해버렸더니 제출하자마자 틀렸었다

1. 테이블 정의
   d[i] : list[i] 탐색할 때의 누적합의 최댓값

2.초기값 설정
d[0] = list[0]
최댓값중 최댓값(출력할값)을 받기 위한 max 초기화

3. 점화식
   이전 d[i]값들 중 최댓값을 선택해 더한다 = d[i]는 항상 최댓값인 경우의 수들만 저장됨