13398: 연속합2 (DP)

풀이

1912: 연속합 문제와 연결되는 문제이다. 처음 문제와 다른점은 하나의 수를 제거하는 경우까지 포함해서 생각해야된다는 점이다.

하나를 뺄 수도 있고 안뺄 수도 있으므로 원래의 dp와 하나를 뺀 dp값을 계산해야 하므로 2차원 배열의 dp를 사용한다.

dp[1][i] = dp[1][i-1] + arr[i]

	10	-4	3	1	5	6	-35	12	21	-1
dp[0]	10	6	9	10	15	21	-14	12	33	32
0	0	-4	3	4	9	15	-20	12	33	32
1	10	10	13	14	19	25	-10	12	33	32
2	10	6	6	7	12	18	-17	12	33	32
3	10	6	9	9	14	20	-15	12	33	32
4	10	6	9	10	10	16	-19	12	33	32
5	10	6	9	10	15	15	-20	12	33	32
6	10	6	9	10	15	21	21	33	54	53
7	10	6	9	10	15	21	-14	-14	21	20
8	10	6	9	10	15	21	-14	12	12	11
9	10	6	9	10	15	21	-14	12	33	33

코드

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[2][N];

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

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

		int max = dp[0][0];
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < N; j++) {
				max = Math.max(dp[i][j], max);
			}
		}
		System.out.println(max);
	}
}