백준 1912 : 연속합 _자바 Java

https://www.acmicpc.net/problem/1912

1912번: 연속합

---

연속되는 수열의  합을 구해 서로 비교 해야 한다. 

arr[i]	10	-4	3	1	5	6	-35	12	21	-1
dp[i]	10	6	9	10	15	21	-14	12	33	32

1. 앞에서 부터 더해진 값에 해당 값을 더했을 때 vs 해당 값에서 다시 합을 시작할 때 

 

 예를 들어, 

arr[6]= -35, 누적 합= -14

arr[7]=12,  -14+12=-2 < 12 

그래서 dp[7]= 12.

 

연속 된 수의 최대 값은 33 이다. 

 

---

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

public 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[] dp=new int[N];
		int[] arr=new int[N];
		int max=Integer.MIN_VALUE;
		String[] str = br.readLine().split(" ");
		
		for(int i=0;i<N;i++)
			arr[i]=Integer.parseInt(str[i]);
				
		
		dp[0]=arr[0];
		
		for(int i=1;i<N;i++) {
			dp[i]=arr[i];
			dp[i]=Math.max(dp[i]+dp[i-1],dp[i]);
		}
			
		for(int i : dp)
			max= Math.max(i, max);
		
		System.out.println(max);
	}// main()
	
	
}// class Main