[백준] 1912번: 연속합

연속합2 문제로 알골골골골대던 중 이거의 이전 문제인 연속합을 먼저 풀었다.

이 문제는

이런 문제였습니당.

연속합 중 가장 최댓값을 찾기 위해서는 각 순서에서

1. 앞의 결과에 계속 더하거나,
2. 그 자리에서부터 연속합을 다시 센다.

이렇게 두 가지 선택지가 있다. 반복문 안에서는 이 두 선택지 중 더 큰 걸 dp에 저장해주면 된다. 정말 쉬운 문제였는데 내가 틀렸던 이유는요

수는 한 개 이상 선택해야한다 는 조건 때문이었다요 😱

반복문을 돌려 dp를 구한 이후에 그 배열의 최댓값을 출력하면 안된다. 반복문 내에서 답을 갱신해야 한다. 비슷한 문제가 하나 더 있었지! 👉🏻 가장 긴 감소하는 부분 수열

그러면 자동적으로 모두 음수인 수열에서는 그 수열의 최댓값이 max에 저장된다.

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

public class Boj1912 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        StringTokenizer st = new StringTokenizer(in.readLine());
        int[] seq = new int[N+1];
        for(int i = 1; i <= N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }
        int[] dp = new int[N+1];
        int sol = seq[1]; // 무조건 하나는 골라야한다고 했으니까 첫 원소로 지정해주고
        for(int i = 1; i <= N; i++) {
            dp[i] = Math.max(dp[i-1]+seq[i], seq[i]);
            sol = Math.max(sol, dp[i]); // 계속 갱신한다.
        }
        System.out.println(sol);
    }
}

---

처음에는 이렇게 해서 틀렸다.

int[] dp = new int[N+1];
for(int i = 1; i <= N; i++) {
    dp[i] = Math.max(dp[i-1]+seq[i], seq[i]);
}
String sol = Integer.toString(Arrays.stream(dp).max().getAsInt());