백준 1912 연속합 JAVA (DP)

1. 문제

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

1912번: 연속합

 

2. 설명

dp[i-1] + arr[i] 와 arr[i] 를 비교했을 때, arr[i]값이 더 크면 이 전에 더해왔던 연속합들을 버리고 다시 i부터 시작하면 된다.

dp[n]이 아니라 중간에서 최댓값이 나올 수 있기 때문에 max를 두어 dp[i]의 최댓값을 삽입!

 

3. 코드

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

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