[13398번] 연속합 2 ( DP, 왼쪽에서 오는 배열과 오른쪽에서 가는 배열 2개, 약간 슬리이딩 DP 느낌 )

✅ 오류 코드

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

public class Main {
	static ArrayList<Integer> list = new ArrayList<>();
	static int[] dp;


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		int min = 0;
		for (int i = 1; i < n; i++) {
			if (list.get(min) > list.get(i)) {
				min = i;
			}
		}
		if (list.get(min) < 0) {
			list.remove(min); //인덱스가 안에
		}
		dp = new int[list.size()];
		dp[0] = list.get(0);
		for (int i = 1; i < dp.length; i++) {
			dp[i] = dp[i - 1] + list.get(i);
		}
		int max = 0;
		for (int i = 0; i < dp.length; i++) {
			if (max < dp[i]) {
				max = dp[i];
			}
		}
		System.out.println(max);
	}
}

✅ 코드

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

public class Main {
	static int[] A;
	static int[] dpL;
	static int[] dpR;


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		A = new int[n];
		dpL = new int[n];
		dpR = new int[n];

		for (int i = 0; i < n; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		dpL[0] = A[0];
		dpR[n - 1] = A[n - 1];

		int result = dpL[0];
		for (int i = 1; i < n; i++) {
			dpL[i] = Math.max(A[i], A[i] + dpL[i - 1]);
			result = Math.max(result, dpL[i]);
		}

		for (int i = n - 2; i >= 0; i--) {
			dpR[i] = Math.max(A[i], A[i] + dpR[i + 1]);
		}

		for (int i = 1; i < n - 1; i++) {
			int temp = dpL[i - 1] + dpR[i + 1];
			result = Math.max(temp, result);
		}
		System.out.println(result);


	}
}