[백준] 1912 : 연속합 - JAVA

solved ac 실버2 (DP)

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

 

 

 

# 문제

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

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

 

# 예제

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

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

 

 

출력 

33

 

 

# 필요개념

처음에는 음수를 기준으로 배열을 만들어 합이 가장 큰 덩어리를 출력하려 했는데, 

3 5 -2 6 8 인 경우 위와 같이 하면 14가 나오지만, 사실 처음부터 끝까지 더하면 20이 나온다.

 

그래서 생각한 방법은, 음수가 나왔을 때로 끊되, 음수까지의 합이 양수가 된다면 초기화하지 않고 계속 더하는 식으로 풀기로 했다.

 

예를 들면 2 3 -2 5 7 인 문제는 2, 3, -2의 합이 양수이므로 다음 덩어리인 5, 7까지 이어서 더한다.

하지만 2, 3, -8, 2, 5 의 경우에는 2, 3, -8의 합이 음수이므로 버리고 2, 5의 합만 이용한다.

 

 

# Code

import java.util.*;
import java.io.*;

import static java.lang.Math.*;

public class Main {

    static int[] arr;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        boolean isAllMinor = true;
        for (int i = 0 ; i < n ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (arr[i] >= 0) isAllMinor = false;
        }

        int idx = 0;
        int max = 0;
        int sum = 0;
        while (idx < n) {

            if (isAllMinor) {
                max = Arrays.stream(arr).max().getAsInt();
                break;
            }
            if (sum + arr[idx] < 0) {
                max = max(sum, max);
                sum = 0;
                idx++;
            } else {
                sum += arr[idx];
                max = max(sum, max);
                idx++;
            }
        }
        System.out.println(max);



    }
}

 

# 결과