[BOJ] 1912 : 연속합 - java

문제

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

---

문제풀이

nowMax : 현재 위치까지의 최대 부분 배열 합을 저장
overMax : 지금까지 발견된 전체 최대 부분 배열 합을 저장
초기값으로 첫 번째 요소를 설정

배열의 두 번째 요소부터 순회하며, 현재 요소를 시작으로 새로운 부분 배열의 합(arr[i])과 이전 부분 배열에 현재 요소를 추가한 합(nowMax + arr[i]) 중 더 큰 값을 nowMax에 저장
overMax는 nowMax와 비교하여 더 큰 값을 저장하여 전체 최대 부분 배열 합을 유지

---

소스코드

import java.io.*;
import java.util.StringTokenizer;

public class _1912 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int nowMax = arr[0];
        int overMax = arr[0];

        for (int i = 1; i < n; i++) {
            nowMax = Math.max(arr[i], nowMax + arr[i]);
            overMax = Math.max(overMax, nowMax);
        }

        bw.write(overMax + "\n");
        bw.flush();
        br.close();
    }
}

---

etc

알고리즘 분류 : 다이나믹 프로그래밍, 카데인 알고리즘

https://djun95.tistory.com/22