백준 13398 : 연속합 2

문제 링크

---

접근 방법

DP(다이나믹 프로그래밍)로 풀이하였다.

 

수를 제거하지 않았을 때 최대 누적합은 sum[]에,

수를 하나 제거했을 때 최대 누적합을 sumR[]에 저장하고

누적합들 중 최대를 출력하면 된다. 

sum[i] = Math.max(0, sum[i-1]) + num[i];

일반 누적값은 이전값에 현재값을 더해준다. 이전값이 음수라면 새로 시작하면 된다. (최대 누적합)

sumR[i] = Math.max(sumR[i - 1] + num[i], sum[i - 1]);

수를 제거했을 때는 현재위치를 제거했을 때 값 sum[i-1]과

이전에 제거한 최대를 유지하고 현재를 더한 sumR[i]+num[i] 중 큰 값을 대입해주면 된다.

---

삽질했던 부분

수를 제거하지 않았을 때 연속되어야 한다는 생각 때문에 Math.max(0, sum[i-1])을 놓쳐서 오래걸렸다.

연속되더라도 이전의 누적값이 음수라면 누적하지 않고 새로 시작하면 된다!

---

후기

DP 문제를 풀 때 시간도 오래 걸리고 오류잡는데도 오래걸려서

연습을 더더더 많이 해야겠다고 생각했다.

---

코드

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

/*
 *  13398. 연속합2
 *  https://www.acmicpc.net/problem/13398
 *  Math.max(0, sum[i - 1]) 을 놓쳐서 풀이하는데 오래걸렸다.
 *  제거를 안했을때도 이전의 누적값이 음수라면 더해줄 필요가 없다!
 */
public class Main {
	static int n, ans, num[], sum[], sumR[];

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