[Gold V] 연속합 2 - 13398

문제 링크

성능 요약

메모리: 24532 KB, 시간: 248 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 7월 7일 02:07:12

문제 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이 (DP 방식)

[연속 합2 풀이] 를 보고 아이디어를 얻었다. 이 방식말고 2차원 배열을 사용하는 방식도 있으므로 참고하면 좋다.

DP 배열 2가지를 사용해서 하나는 시작 부분을 기준으로, 하나는 끝 부분을 기준으로 최대를 계산한다.

또, 수열에서 수를 하나 제거할 수 있다. 는 코멘트에 따라, 시작 DP 배열과 끝 DP 배열에서 인덱스를 숫자 하나만 없도록 조정해, 최대를 계산하는 방식이다.

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

public class Main {
	//DP 문제
	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		int[] dp_front = new int[n]; //앞에서부터 누적시킬 DP
		int[] dp_end = new int[n]; //뒤에서부터 누적시킬 DP
		int[] arr = new int[n]; //배열
		
		StringTokenizer st =new StringTokenizer(br.readLine()); //입력받기
		for(int i=0; i<n; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		dp_front[0] = arr[0];
		int ans=dp_front[0];
		for(int i=1; i<n; i++) { //앞에서부터 최대 계산
			dp_front[i] = Math.max(dp_front[i-1]+arr[i], arr[i]);
			
			ans = Math.max(ans, dp_front[i]);
		}
		
		dp_end[n-1]=arr[n-1];
		for(int i=n-2; i>=0; i--) { //뒤에서부터 최대 계산 
			dp_end[i]=Math.max(dp_end[i+1]+arr[i], arr[i]);
		}
		
		for(int i=1; i<n-1; i++) {//ANS가 최대 VS 중간에 숫자 하나 지우고 계산한 것이 최대인지 판별
			ans = Math.max(ans, (dp_front[i-1]+dp_end[i+1]));
		}
		System.out.println(ans);	
	}
}