글 읽기 - 가장 큰 증가 부분 수열 .. 예외가 있을까요..

aod0326 7년 전 0

가장 긴 증가 부분 수열에서 정답 나온 코드에다가

sum[] 만 추가 시킨건데 틀렸다고 나오네요...ㅠㅠ

어디가 틀린걸까요..

예시 이것저것 다 넣어봐도 잘나오던데..

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int num[] = new int[N];
        Random r = new Random();
        int D[] = new int[N];
        for(int i=0;i<N;i++)
        	num[i] = sc.nextInt();
        int sum[] = new int[N];
        for(int i=0;i<N;i++){
        	int max = 0;
        	int max_num = 0;
        	int count = 0;
        	for(int j=0;j<i; j++){
        		if(num[j] < num[i]){
        			if(D[j] >= max_num){
        				max_num = D[j];
        				max = j;
        				count++;
        			}
        		}
        	}
        	if(count == 0){
        		D[i] = 1;
        		sum[i] = num[i];
        	}else{
        		D[i] = D[max] + 1;
        		sum[i] = sum[max] + num[i];
        	}
        }
        int max = 0;
        for(int i=0;i<N;i++){
        	if(sum[i] >= max)
        		max = sum[i];
        }
        System.out.println(max);   
    }
}

kesakiyo 7년 전 0

D를 증가하는 부분수열의 최대 길이로 잡지말고

증가하는 부분수열의 최대 합으로 잡으세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

가장 큰 증가 부분 수열 .. 예외가 있을까요..

aod0326 7년 전 0

kesakiyo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말