연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일 매일 수익을 적어놓았다.
어느 날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다.
오늘이 창업한지 6일 되었고, 수익이 다음과 같다고 하자.
이때, 가장 많은 돈을 번 구간은 2~6까지이고 총 수입은 14이다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 ≤ N ≤ 250,000) 둘째 줄부터 N개의 줄에는 매일 매일의 수익 P가 주어진다. (-10,000 ≤ P ≤ 10,000) 수익은 첫 날부터 순서대로 주어진다. 입력의 마지막 줄에는 0이 주어진다.
각 테스트 케이스에 대해서 가장 많은 수익을 올린 구간의 수익을 출력한다. 단, 구간이 비어있으면 안 된다.
6
-3
4
9
-2
-5
8
2
-1000
-19
0
14
-19
이 문제는 다이나믹 프로그래밍 알고리즘을 이용해서 풀 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N;
int[] arr;
int max;
StringBuilder sb = new StringBuilder();
while(true){
N = Integer.parseInt(br.readLine());
if(N==0) break;
arr = new int[N];
max = Integer.MIN_VALUE;
for(int i=0; i<N; i++) {
int x = Integer.parseInt(br.readLine());
arr[i] = x;
if(i>0) {
int y = arr[i-1];
if(x+y>x) { //직전 값과 현재 idx의 값을 더한게 더 클 때
arr[i] = x+y;
}
}
max = Math.max(max, arr[i]);
}
sb.append(max).append("\n");
}
System.out.print(sb);
}
}