[백준] 1912 : 연속합 (JAVA)

1912번: 연속합

간단한 dp 문제인데 dp 문제는 족족 틀린다.. 연습이 많이 필요한 부분이다..

 

 

간단하게 생각하면 쉬운 문제이다.

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

dp[i] 는 (i-1까지 누적된 dp) + (arr[i]) 와 arr[i] 중 큰 값을 저장한다.
이후 dp 에 저장된 값 중 가장 큰 것이 답이 된다.

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

class Main
{

	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		st=new StringTokenizer(br.readLine()," ");
		
		int[] arr = new int[N];
		int[] dp =new int[N];
		for(int i=0;i<N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		dp[0]=arr[0];
		for(int i=1;i<N;i++) {
			dp[i]=Math.max(dp[i-1]+arr[i], arr[i]);
		}
		
		int ans=Integer.MIN_VALUE;
		for(int x:dp) {
			ans=Math.max(ans, x);
		}
		System.out.print(ans);
	}
}