백준 1912 연속합

문제보기 

연속합을 구할때 유의할점은 

음수를 포함해도 답이 될때가 있다는 것이다. 

예를 들어 10 -1 11 일때, 음수를 포함하지 않으면 답이 나오질 않는다. 음수를 포함해서 10 + (-1) + 11 이 되어야만 가장 큰 연속합이된다.

D[i]는 A[i]로 끝나는 최대 연속합을 저장하는 배열이다. 

1. A[i-1]로 끝나는 연속합에 , A[i]가 포함된다. 

2. 1번의 경우보다 A[i]가 큰 경우이다. 

이 두개의 경우로 식을 세우면 된다.

D[i] = Math.max(A[i],D[i-1]+A[i])

시간복잡도는 O(N)이다. N번의 횟수와 계산식2개면 되니까! 

package Problems;
/**
 * 
 * 백준 1912 연속합 
 * 
 * 동적 계획
 * 
 */
import java.util.Scanner;
 
public class Boj1912dp {
    
    public static int n,arr[],dp[];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        
        for(int i = 1; i < n+1; i++) {
            arr[i] = in.nextInt();
        }
        
        for(int i = 1; i < n+1; i++) {
            
            dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);
            
        }
        
        int ans = dp[1];
        
        for(int i = 1; i < n+1; i++) {
            
            if(ans < dp[i]) {
                ans = dp[i];
            }
        }
        
        System.out.println(ans);
        
    }
 
}