129. 1912(연속합)

import java.util.*;
import java.io.*;
import java.math.BigInteger;

class Main {
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		String[] tmp = br.readLine().split(" ");
		
		for(int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(tmp[i]);
		}
		
		for(int i = 1; i < N; i++) {
			num[i] = Math.max(num[i], num[i-1]+num[i]);
		}
		
		Arrays.sort(num);
		
		System.out.println(num[N-1]);

	}

}

문제요약

모든 경우의 연속된 수를 더 했을 때 가장 큰 수가 무엇인가? 

설명

리스트의 크기는 상관 없다.

들어온 입력의 리스트 만큼 사용할 것이다.

다음과 같이 숫자(현재 인덱스) 값과 숫자(현재 인덱스) + 숫자(현재 인덱스 - 1) 의 값 중 더 큰 것을 비교하여 본래 리스트에 덮어 씌운다.

 

예를들어 num[4]번째 에서 3번째 인덱스 값은 0 , 1 , 2 를 합 했을 경우 가장 큰 수를 나타낸다.

num[4] 입장에서는 자기 자신의 값 혹은 num[3]의 값 중 더 큰 것을 index = 4 (num[4]) 에 저장하면서 다음 값으로 진행한다.

 

즉, 최종 결과에서 각 인덱스의 값은 자기 자신의 인덱스 까지 연속된 합의 수중에서 제일 큰 수를 나타내는 것이다.

 

그 결과 중 가장 큰 수를 뽑는다면 제시된 수 중의 연속된 합 중에서 가장 큰 수를 뽑는 것이다.