DP :: 백준 :: 연속합 :: 1912

연속합 1912

https://www.acmicpc.net/problem/1912

[문제 풀이]

dp[i]를 index가 i일때의 연속합이라고 정의하면

    dp[i] = max(ar[i], dp[i-1]+ar[i])

이런 점화식을 구할 수 있다.

우선 10개의 숫자가 입력됐을 때 방금 구한 점화식으로 연속합을 구해보면

index	1	2	3	4	5	6	7	8	9	10
입력	10	-4	3	1	5	6	-35	12	21	-1
연속합	10	6	9	10	15	21	-14	12	33	32

표와 같고, 연속합의 최댓값은 index가 9일때 33(12+21)이라는 것을 알 수 있다.

계산을 모두 마친 후, dp배열에 저장된 연속합들 중 가장 큰 값을 출력하면 끝!!

import java.io.BufferedReader;
import java.io.InputStreamReader;
  
public class Main {
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        String[] tmp = br.readLine().split(" ");
        int[] ar = new int[num+1];
        int[] dp = new int[num+1];
        int max = Integer.MIN_VALUE;
        for(int i=1;i<=num;i++){
            ar[i] = Integer.parseInt(tmp[i-1]);
        }
        for(int i=1;i<=num;i++){
            dp[i] = Math.max(ar[i], dp[i-1]+ar[i]);
            max = max > dp[i] ? max : dp[i];
        }
         
        System.out.println(max);
    }
}

※풀이 과정에 문제가 있으면 언제든 지적 받습니다!※