[JAVA] 백준 13398번 : 연속합 2

 

---

 

• 코드

정답 코드 : 기존 연속합 문제에서 다른 점은 최소값 수 하나를 제거할 수 있다는 점! 그래서 기존 연속합 코드에서 DP하나를 더 추가해 최소값을 하나 제외했을 때의 최대값도 유지시켜 주었다.

 

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] array = new int[n];
        int [] dp = new int[n];
        int [] dp2 = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) 
        	array[i] = Integer.parseInt(st.nextToken());
        
       
        dp[0] = array[0];
        dp2[0] = array[0];
	    int max = array[0];
	    for(int i=1; i<n; i++){
	    	 dp[i] = Math.max(dp[i-1] + array[i], array[i]);
	    	 dp2[i] = Math.max(dp2[i-1] + array[i], dp[i-1]);
	         
	         max = Math.max(max, Math.max(dp[i],dp2[i]));
	    }

	    System.out.println(max);
    }
}