사용한 것
- 구간의 최대 합을 구하기 위한 bottom-up
풀이 방법
arr
에 숫자 입력 받음 (인덱스 1부터)
- 인덱스 1부터 구간을 계속 더하거나 새로 시작하거나 둘 중 큰 값 선택
dp
중에 가장 큰 값 선택
코드
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 = new int[N + 1];
String[] line = br.readLine().split(" ");
for(int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(line[i - 1]);
}
int[] dp = new int[N + 1];
for(int i = 1; i <= N; i++) {
dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
}
int max = dp[1];
for(int i = 1; i <= N; i++) {
max = Math.max(dp[i], max);
}
System.out.println(max);
}
}