[백준] 13398 연속합 2 [JAVA]

문제링크 : www.acmicpc.net/problem/13398

13398번: 연속합 2

 

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

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

}