[ BOJ ][JAVA][4097] 수익

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

4097번: 수익

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	392	197	157	50.645%

문제

연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일 매일 수익을 적어놓았다.

어느 날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다.

오늘이 창업한지 6일 되었고, 수익이 다음과 같다고 하자.

• 1일: -3
• 2일: 4
• 3일: 9
• 4일: -2
• 5일: -5
• 6일: 8

이때, 가장 많은 돈을 번 구간은 2~6까지이고 총 수입은 14이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 ≤ N ≤ 250,000) 둘째 줄부터 N개의 줄에는 매일 매일의 수익 P가 주어진다. (-10,000 ≤ P ≤ 10,000) 수익은 첫 날부터 순서대로 주어진다. 입력의 마지막 줄에는 0이 주어진다.

출력

각 테스트 케이스에 대해서 가장 많은 수익을 올린 구간의 수익을 출력한다. 단, 구간이 비어있으면 안 된다.

예제 입력 1

6
-3
4
9
-2
-5
8
2
-1000
-19
0

예제 출력 1

14
-19

코드

/*
    수익
    DP or 구현
*/
import java.io.*;
import java.util.*;

public class p4097 {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;

            int sum = 0;
            int max = Integer.MIN_VALUE;
            for (int i = 1; i <= n; i++) {
                int number = Integer.parseInt(br.readLine());
                sum += number;
                max = Math.max(max, sum);

                if (sum < 0) sum = 0;
            }

            System.out.println(max);
        }
    }
}