[Java] 백준 1912번 : 연속합

문제소개

 

해결과정

최초 접근은 투 포인터를 떠올렸다.

하지만, 명확하게 언제 start, end 포인터를 옮기며 판단해야하는지 떠오르지 않았다.

이후 DP를 활용해 문제를 접근하기로 했다.

 

DP를 활용한 풀이의 핵심은 현재 위치까지의 누적합이 현재 위치의 단일값과 비교했을 때 더 큰지 판단하는 것이다.

누적합이 더 크다면 해당 dp배열에 누적합을 넣어주면 되고, 단일값이 더 크다면 해당 누적합은 더 이상 최댓값을 만족하지 못하기 때문에 dp배열에 단일값을 넣어준다.

 

이렇게 구해진 dp배열 중 최댓값을 찾는다면 해당 값이 임의의 구간에서 최댓값을 의미하게 된다.

 

feat: 최근 자바 8의 스트림, 람다를 학습하고 있어 코드에 적용할 수 있다면 최대한 적용해보려고 연습하고 있습니다. 적절한 활용이 아닐 수 있다는 점 양해부탁드립니다^^.

 

솔루션

package DP.백준1912_연속합;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

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());
        List<Integer> list = Arrays.stream(br.readLine().split(" "))
                .map(w -> Integer.parseInt(w))
                .collect(Collectors.toList());

        int[] dp = new int[N + 1];
        Arrays.fill(dp, -2000);

        for (int i = 1; i <= N; i++) {
            dp[i] = Math.max(dp[i - 1] + list.get(i-1), list.get(i-1));
        }

        int max = Arrays.stream(dp)
                .max()
                .orElse(-1);
        System.out.println(max);

    }
}