1912

연속합

 

이전합+현재값(dp[1-i] + arr[i])이 음수가 되면, 현재값 dp[i]는 arr[i]가 된다.

 

작은 아이디어 하나면 끝

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

public class Main {
	static Integer[] arr;
	static Integer[] dp;

	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());
		arr = new Integer[N];
		dp = new Integer[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; ++i)
			arr[i] = Integer.parseInt(st.nextToken());

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

		System.out.println(max);
		br.close();

	}

}

ex) 
10
2 1 -4 3 4 -4 6 5 -5 1
14