[백준 1912번] 연속합 - java

문제 설명

1. N개의 숫자를 입력받는다.

2. 숫자들의 합을 구해서 최소숫자를 return하면 된다.

3. 최소 1000 최대 1000까지 간다.

풀이 과정

 1. DP를 통해 쉽게 구할 수 있다.

 2. 계속 숫자가 커지도록 만들기만 하면 부분합들을 구할 수 있다.

 3. DP배열에 현재 숫자를 더했을 때 만들어지는 최대 합을 구하면 된다. 그 방법은 이전 숫자가 양수이면 그곳에 지금수를 더하고, 음수면 0에다가 더하면 된다.

ex) 2, 3, -6, 3, -2, 4가 주어지는 경우의 합은 -> 2, (2+3), (2+3-6), 3, (3-2), (3-2+4) 앞의 숫자가 0보다 작으면 없애고 그보다 크면 쓰면 된다.

 4. 구해진 합들 중 최대값을 return하면 된다.

 

코드

mport 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]; // 수
		int sum[] = new int[N]; // 합
		
		for(int i=0; i<N; i++)num[i] = sc.nextInt();  // 수 입력
		
		sum[0] = num[0];  // 처음 수
		for(int i=1; i<N; i++) {
			sum[i] = num[i]+Math.max(sum[i-1], 0);  // 이전까지 만든 숫자가 0보다 크면 지금 숫자를 더하면 이전보다 큰 숫자가 될것이다. 만약 안된다면 다시 새로운 합을 만들어야 할 것이다.
		}
		
		int ans = -1000;  // 최소숫자 1000
		for(int i=0; i<N; i++) ans = Math.max(ans, sum[i]); // 최대 부분합을 구하면 된다.
		
		System.out.println(ans);
	}
	
}