백준 1912번_연속합_java

문제

풀이

동적계획법을 이용
동적계획법 : 특정 범위까지의 값을 구하기 위해 그것과 다른 범위의 값을 이용해서 효율적으로 구하는 방법

아래의 조건을 모두 만족할 경우에는 i번째 위치까지의 연속합은 i-1번째 위치까지의 연속합과 i번째 값의 합
(i-1번째 까지의 합이 양수 && i-1번째 까지의 연속합과 i번째 값의 합이 양수일 경우)
이외의 경우는 i번째 까지의 연속합은 i번째 값으로

추가로 dp[i] < dp[i-1] 일 수 있으므로 dp[i] 값과 max값을 비교하는 로직 필요
ex) 10 -4
dp[0] = 10
dp[1] = 6

코드

package acmicpc;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.stream.Stream;

public class acmicpc1912 {
	public static void main(String[] agrs) {
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

			int n = Integer.parseInt(reader.readLine());
			int numArr[] = Stream.of(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			
			int dp[] = new int[n];
			dp[0] = numArr[0];
			int max = dp[0];
			
			for(int i=1; i<n; i++) {
				if(dp[i-1] > 0 && dp[i-1] + numArr[i] > 0) {
					dp[i] = dp[i-1] + numArr[i];
				} else {
					dp[i] = numArr[i];
				}
				
				if(max < dp[i]) {
					max = dp[i];
				}
			}
			
			writer.append(String.valueOf(max));
			writer.flush();
			writer.close();
		} catch (Exception e) {
			
		}
	}
	
}