문제 풀이(57)

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

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



public class Main {

    static int n;
    static int[] D;
    static int[] A;

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        n = Integer.parseInt(br.readLine());

        A = new int[n];

        D = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        D[0] = A[0];

        for (int i = 1; i < n; i++) {
            D[i] = Math.max(A[i], D[i-1] + A[i]);
        }

        Arrays.sort(D);

        System.out.println(D[n - 1]);
    }
}

n은 배열 A에 저장될 정수의 개수를 나타낸다.

배열 A는 사용자로부터 입력 받은 연속된 정수들을 저장한다.

배열 D는 각 인덱스에서 끝나는 최대 부분 배열의 합을 저장한다. D[i]는 배열 A의 0번째 인덱스부터 i번째 인덱스까지의 부분 배열 중 합이 최대인 배열의 합을 의미한다.

초기 조건으로 D[0]은 A[0]으로 설정한다. 이는 첫 번째 요소가 포함된 최대 부분 배열의 합이 첫 번째 요소 자체임을 의미한다.

for 루프는 D 배열을 채우는 데 사용된다. 각 인덱스 i에 대해, D[i]는 A[i]와 D[i-1] + A[i] 중 큰 값을 취한다. 이는 i번째 요소를 포함하는 최대 부분 배열이 i번째 요소만을 포함할지, 아니면 i-1번째 요소까지 포함하는 부분 배열에 i번째 요소를 추가하여 확장할지를 결정한다.

Arrays.sort(D)는 D 배열을 오름차순으로 정렬한다. 정렬 후, D[n - 1]는 가장 큰 값, 즉 최대 부분 배열의 합이 된다.

마지막으로, System.out.println(D[n - 1])는 계산된 최대 부분 배열 합을 출력한다.