글 읽기 - 1912 연속합 반례를 못찾겠습니다. 도와주세

lhs1543 6년 전 0

대략적인 아이디어는

1) 첫항이 0이상인 경우 (답이 0 이상임을 보장)

0이상의 값들을 더해 나가다가 음수가 나오면, 음수가 나오기 전까지 더한 값을 array에 저장

array내림차순 정렬 후 첫번째 인덱스값 인출

2) 첫항이 음수인경우

1. 모든항이 음수인경우 -> 모든 항 중 가장 큰 값을 결과값으로 인출

2. 하나라도 0이상인 경우 -> 1) 방식과 동일

아이디어가 좀 좋지 않아도.. 도와주실분ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Sum {

	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int initial = Integer.parseInt(br.readLine());
		
		String[] sSequence = br.readLine().split(" ");
		int[] sequence = new int[initial];
		
		for(int i = 0; i < sequence.length; i++) {
			sequence[i] = Integer.parseInt(sSequence[i]);
		}	
		
		int result = sequence[0];
		ArrayList<Integer> max = new ArrayList<Integer>();
		
		//첫항이 음수가 아님(결과가 최소 0이상임)
		if(sequence[0] >= 0) {
			for(int i = 1; i < sequence.length; i++) {
				
				if(sequence[i] >= 0) {
					result += sequence[i];
                    
				} else {
					max.add(result);
					result = 0;
                }		
			}
			max.add(result);
				
		//첫항이 음수임
		} else {
			boolean allMinus = true;
			for(int i = 1; i < sequence.length; i++) {
				if(sequence[i] >= 0) {
					allMinus = false;
				}				
			}
			
			//모든항이 음수인 경우는 음수들 중 가장 큰놈 한개가 답
			if(allMinus) {
				for(int i = 1; i < sequence.length; i++) {
					if(sequence[i] > result) {
						result = sequence[i];
					}
				}
				max.add(result);
				
			//모든항이 음수가 아닌경우 -> 답이 0 이상임을 보장
			} else {
				result = 0;
				for(int i = 1; i < sequence.length; i++) {
					if(sequence[i] >= 0) {
						result += sequence[i];
					} else {
						max.add(result);
						result = 0;
					}
				}
				max.add(result);
			}
		}
		
        Collections.sort(max, new Comparator<Integer>(){

			@Override
			public int compare(Integer arg0, Integer arg1) {
				return arg1.compareTo(arg0);
			}	
        });
        
        System.out.println(max.get(0));
	}
}

chogahui05 6년 전 2

반례 데이터 드리겠습니다.

3 9 -8 6 4 -7 5 -4 4 -2 5

답 : 15

출력하는 답 : 12

lhs1543 6년 전 0

앗 .. 이런 완전 문제를 잘못파악했네요.. 감사합니다.

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

문제

문제

출처

ICPC

1912 연속합 반례를 못찾겠습니다. 도와주세

lhs1543 6년 전 0

chogahui05 6년 전 2

lhs1543 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말