acmicpc

[BAEKJOON] 1912. 연속합

코드와이 2021. 4. 5. 22:52

 

DP

문제링크

www.acmicpc.net/problem/1912

 

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

 

package acmicpc.Silver2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 연속합 {

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