백준 1912

문제

---

Code

package test;

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

public class P1912 {
	
	private static int[] seq;
	private static Integer dp[];
	private static int max;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		seq = new int[n];
		dp = new Integer[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < n; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0] = seq[0];
		max = seq[0];
		
		maxSum(n - 1);
		System.out.println(max);
	}
	private static int maxSum(int n) {
		if(dp[n] == null) {
        	/*
            	연속된 수의 합이기 때문에 이전의 합보다 더 큰 수가 나타나면
                이전의 합은 필요없어진다.
                
            	따라서 (이전 탐색과 n 번째 항의 합)과 n 번째 항을 비교
                --> 그 중 큰 값을 dp에 저장
                
                dp[n]과 기존의 최대 합을 비교해 큰 값으로 갱신
            */
			dp[n] = Math.max(maxSum(n - 1) + seq[n], seq[n]);
			max = Math.max(dp[n], max);
		}
		return dp[n];
	}

}

---

참고 : https://st-lab.tistory.com/140