[Baekjoon Online Judge] 1912번: 연속합

1912번: 연속합

요구사항

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

입력

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

출력

 - 첫째 줄에 답을 출력한다.

---

 n개의 정수로 이루어진 임의의 수열 중 연속 된 몇 개의 수의 합 중 가장 큰 합을 찾아야 한다. dp 테이블을 활용하여 해당 자리까지 가장 큰 값을 채워가야 한다.

 

 가장 큰 값을 얻기 위해서는 이전 dp 값 + 현재 sequence 값과 현재 sequence 값을 이전 dp 값에 비교해야 한다.

 

10	-4	3	1	5	6	-35	12	21	-1
10

 위의 값들은 수열의 값이고, 밑은 dp 값을 저장하는 공간이다. 10의 경우 그 자체가 가장 큰 값이기 때문에 10을 채워둔다.

 

10	-4	3	1	5	6	-35	12	21	-1
10	6

 

 이제부터 일정한 규칙에 따라 dp 테이블을 채워가야 한다. 이전 dp 값 + 현재 sequence 인 10 - 4와 현재 sequence 값인 -4를 비교하여 둘 중 큰 값을 dp 테이블에 채워간다.

 

10	-4	3	1	5	6	-35	12	21	-1
10	6	9	10	15	21	-14

 

 지속적으로 채워가던 중 -14 + 12 와 12를 비교하면 현재 sequence 값이 더 크기 때문에 연속된 수가 초기화 되고 12 부터 다시 값을 dp 테이블에 채워간다.

 

10	-4	3	1	5	6	-35	12	21	-1
10	6	9	10	15	21	-14	12	33	32

 

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

public class Baekjoon1912 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine());
        String[] input = bufferedReader.readLine().split(" ");

        int[] sequence = new int[n];
        int[] dp = new int[n];

        for (int i = 0; i < sequence.length; i++)
            sequence[i] = Integer.parseInt(input[i]);

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                dp[i] = sequence[i];
                continue;
            }

            if (sequence[i] <= dp[i - 1] + sequence[i])
                dp[i] = dp[i - 1] + sequence[i];
            else
                dp[i] = sequence[i];
        }

        Arrays.sort(dp);

        System.out.println(dp[n - 1]);

        bufferedReader.close();
    }
}

 

 모든 값을 dp 테이블에 작성한 뒤 dp에서 가장 큰 값을 찾아 출력하면 된다.