글 읽기 - 연속합 문제에 대한 반례가 있을까요 ? 오류 원인을 못찾겠어요.

chabt 4년 전 0

연솝합 알고리즘을 아래와 같이 구현해 봤는데요. 오류가 떨어집니다.

혹시 반례가 있을까요 ?

import java.io.*;
import java.util.*;

public class DP_연속합_1912 {
	static int DEBUG=1;
	static int N;
	static long[] dp;

    public static void main(String[] args) throws Exception {
    	exec_prepocess("DP_연속합_1912");
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
    	StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());

		dp = new long[N+1];
		long sub_sum = 0;

		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			sub_sum += Integer.parseInt(st.nextToken());
			
			dp[i] = Math.max(dp[i-1], sub_sum);
			
			if(sub_sum<0) sub_sum = 0;			
		}
		
    	System.out.println(dp[N]);
    	
    }
    
	private static void exec_prepocess(String fname) throws Exception {
    	String class_name = new Object(){}.getClass().getTypeName();
    	class_name = class_name.substring(0, class_name.length()-2);
    	if(class_name.equals("Main")) DEBUG=0;    	
    	if(DEBUG!=0) { 
    		System.setIn(new FileInputStream(System.getProperty("user.dir") + "\\samples\\" + fname + ".txt"));
    	}		
	}
}
/*
10
10 -4 3 1 5 6 -35 12 21 -1
----
33
*/

luniro 4년 전 0

입력:
5
-1 -2 -3 -4 -5

정답:
-1

luniro 4년 전 0

게시판 검색해서 최근 글 3개만 읽었어도 더 일찍 찾으셨겠네요

chabt 4년 전 0

글을 써놓고 나중에 생각해보니.. 음수가 나올 경우는 문제가 되겠구나 라고 생각이 들긴 했습니다.

댓글 감사드립니다.

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

문제

문제

출처

ICPC

연속합 문제에 대한 반례가 있을까요 ? 오류 원인을 못찾겠어요.

chabt 4년 전 0

luniro 4년 전 0

luniro 4년 전 0

chabt 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말