1912: 연속합 (DP)

풀이

첫번째 정수부터 체크하여 현재값을 더한 dp 값과 그 전까지의 dp값을 비교하여 큰 것이 현재까지 최대 dp값이 된다.

코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		int[] dp = new int[N];

		for (int n = 0; n < N; n++) {
			arr[n] = sc.nextInt();
		}

		dp[0] = arr[0];
		for (int i = 1; i < N; i++) {
			dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
		}

		int max = arr[0];
		for (int i = 1; i < N; i++) {
			max = Math.max(max, dp[i]);
		}

		System.out.println(max);
	}
}