[자바/그리디] 코드트리. 연속 부분 합의 최댓값 구하기2

문제

문제 링크

해석

누적합이 음수로 변환되는 부분은 계속 더하는 것보다, 다시 구간을 설정하는게 누적합 입장에서 "반드시" 더 좋은 결과가 나올 수 밖에 없다. 따라서 이 문제를 그리디로 풀면 전체 배열을 단 한번만 선형 순회하여 답을 구할 수 있으므로 O(N)으로 도출된다.

코드

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 = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int idx = 0;
        int res = 0;
        int ans = Integer.MIN_VALUE;
        while (true) {
            if (idx == n) {
                break;
            }

            if (res < 0) {
                res = 0;
            }
            res += arr[idx];
            ans = Math.max(ans, res);
            idx++;
        }
        System.out.println(ans);
    }
}