백준-1912번/연속합 (java)

 

크기가 n인 정수 배열 arr[n] 에서 연속된 수의 최대값을 구하기 위해 크기가 n인 정수 배열 dp를 하나 만들어 준다.

 

dp[i] = arr[i]에서의 연속된 최대 합

 

최대 값이 될수 있는 경우는 총 3가지이다.

1) i-1에서의 최대 연속합 + arr[i]

2) 연속된 두 수의 합이 최대인 경우 (arr[i-1]+arr[i])

3) arr[i]가 최대합인 경우

 

이를 점화식으로 만들면 코드는 다음과 같다

 

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

 

정답 코드

 

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

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		long[] arr= new long[n];
		long[] dp=new long[n];
		for(int i=0; i<n; i++) {
			arr[i]=scanner.nextInt();
		}
		for(int i=0; i<n; i++) {
			if(i==0) {
				dp[0]=arr[i];
			}
			else {
				dp[i]=Math.max(dp[i-1]+arr[i],arr[i-1]+arr[i]);
				if(dp[i]<arr[i]) {
					dp[i]=arr[i];
				}
			}
		}
		long big=dp[0];
		for(int i=0; i<n; i++) {
			if(dp[i]>=big) {
				big=dp[i];
			}
		}
		System.out.println(big);
	}
}