[백준 1912] 연속합 (JAVA)

연속합 

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

1912번: 연속합

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

128 MB

115866

41697

29399

34.685%

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

---

N 개의 원소를 가지는 수열에서 연속된 합을 구하였을 때 구할 수 있는 합 중 가장 큰 값을 출력하면 된다.

 

dp[i] 를 시작이 어딘지는 모르겠지만 i 번째 까지의 합 중, 가장 최대의 값이라고 정의하자.

 

그러면 아래와 같은 점화식을 떠올릴 수 있다.

 

dp[ i ] = Max ( dp[i-1] + arr[ i ] , arr[ i ] )

 

말로 풀어서 설명하면,

 

i 번째까지의 최대 합은

i - 1 번째까지 구할 수 있는 최대합에 i 번째의 값을 더한 값과

그냥 i 번째 값 하나를 비교하였을 때 더 큰 쪽이다.

 

이를 구현하여 dp table 을 채운 뒤, 가장 최대의 값을 출력해주면 해결된다.

 

import java.util.Scanner;

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