백준 1912 연속합 Java

정답률 26퍼센트의 dp 문제이다.

연속으로 된 몇 개의 수중 가장 합이 큰 값을 구하는 문제이다.

 

점화식을 구하는 방법을 보면

dp [i]에 올 수 있는 값은

dp[i-1]+값[i]이다.

하지만 값들 중에서 음수가 있기 때문에

dp[i-1]+값[i] 보다 그냥 값[i]가 더 클 수가 있다.

 

그래서 dp[i] = Math.max(dp[i-1]+값[i], 값[i]);로 점화식을 짤 수 있다.

 

백준님의 강의자료 중..

dp[i]엔 연속된 합들이 들어가게 된다. 현재 값과 전에 값을 더했는데 현재 값 보다 작은 경우엔

dp[i]에 그냥 원래 값이 들어간다.

이렇게 구한 dp배열 중 최대 값을 출력하면 된다.

 

코드는 몇 줄 안되는데 생각하기가 참 어려운 문제이다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] a = new int[n];
        int [] dp = new int[n];
 
        for(int i=0; i<n; i++) 
            a[i] = scan.nextInt();
 
        dp[0] = a[0];
        for(int i=1; i<n; i++)
            dp[i] = Math.max(dp[i-1]+a[i], a[i]);
        
        Arrays.sort(dp);
        System.out.println(dp[n-1]);
    }