백준 1912 풀이

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

이어서 푼 문제는 연속합 문제인데 처음에는 2중 for문을 활용해서 풀면 될줄 알았다.

그런데 시간이 1초?!

2중 for문을 사용하면 n^2이라 시간초과가 나겠구나라는 생각을 했고 dp로 풀어야한다는 것까지 생각이 자연스럽게 이어졌다.

dp로 접근하고자 하니 다음은 간단했다.
연속된 수의 합을 구해야하기 때문에

dp[i] = dp[i-1] + arr[i]

와 같은 점화식이 나오고 이 점화식을 기준으로 결정하면 된다.

이 때 만약 dp[i]로 들어갈 dp[i-1]+arr[i]의 값이 arr[i]이하이면 최대를 구해야하는 입장에서 최대가 감소하는 일이 벌어지기 때문에 dp[i] = arr[i]가 되어야한다.
따라서

dp[i-1]+arr[i] <= arr[i] 이면 dp[i] = arr[i]이고
dp[i-1]+arr[i] > arr[i] 이면 dp[i] = dp[i-1]+arr[i]

이다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Optional;

public class Main {
    static int count = 0;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String num = br.readLine();
        int n = Integer.parseInt(num);
        String line = br.readLine();
        String[] nums = line.split(" ");
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(nums[i]);
        }

        int maxN = -1001;
        Integer dp[] = new Integer[n];

        for (int i = 0; i < n; i++) {
            dp[i] = -1001;
        }

        dp[0] = arr[0];
        for (int i = 1; i < n; i++) {
            int next = dp[i - 1] + arr[i];
            if (arr[i] >= next)
                dp[i] = arr[i];
            else if (arr[i] < next) {
                dp[i] = next;
            }
        }

        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(dp));
        Comparator<Integer> comp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 > o2)
                    return 1;
                else
                    return -1;
            }
        };
        Optional<Integer> max = list.stream().max(comp);
        int m = max.get();

        bw.write(Integer.toString(m));

        br.close();
        bw.close();
    }

}