2022-10-17 algorithm

boj_1912 연속합 - silver 2

Link : 연속합

정보

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력1

예제 출력1

풀이

1. 검색을 하여 다른 사람들의 도움을 받았다.
2. 숫자를 담는 배열과 최적의 값을 저장하는 배열을 만든다.
3. 그 다음 index 1 부터 시작해서 앞에 것을 더한 것과 자신의 값을 비교해서 더 높은 값을 해당 index자리에 저장한다.
4. 이 과정을 거치면 해당 인덱스까지 가장 높은 합을 가져올 수 있다.

코드

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

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

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
        dp[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            dp[i] = Math.max(arr[i], dp[i-1] + arr[i]);
        }
        int answer = dp[0];
        for (int i = 1; i < dp.length; i++) {
            if (dp[i] > answer) {
                answer = dp[i];
            }
        }
        System.out.println(answer);
    }
}

결과

tags: algorithm, Boj, dfs