Baekjoon 1912. 연속합 / Java

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

알고리즘 설명

문제 설명

주어진 수열에서 연속된 부분 수열의 합 중 가장 큰 합을 찾는 문제

코드 설명

dp를 활용하여 수열의 최대 부분합을 저장한다.
dp[x] 는 x 위치까지 최대 부분합을 저장한다.
dp[x] 는 dp[x-1] + arr[x], arr[x] 중의 큰 값이 된다.
dp를 활용하여 시간복잡도를 O(n) 으로 해결할 수 있다.

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

public class Main {
    public static int n;
    public static int[] arr;
    
    // 각 위치에서의 최대 부분합을 저장할 배열
    public static int[] dp;
    
    public static int res = Integer.MIN_VALUE;

    public static BufferedReader br;

    public static void main(String[] args) throws IOException {
    	// 입력
        br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // dp 배열 초기화
        dp = new int[n];
        // 첫 번째 원소의 최대 부분합은 자기 자신
        dp[0] = arr[0];
        // 현재까지의 최대 부분합을 첫 번째 원소로 초기화
        res = arr[0];
        // 최대 부분합 계산
        sol(n - 1);

        // 결과 출력
        System.out.println(res);
    }

    public static int sol(int num) {
        // 기저 조건: num이 0이면 arr[0] 반환
        if (num == 0) {
            return arr[0];
        }
        // dp[num]이 아직 계산되지 않은 경우
        if (dp[num] == 0) {
            // num번째 위치의 최대 부분합을 갱신
            dp[num] = Math.max(sol(num - 1) + arr[num], arr[num]);
            // 최대 부분합을 갱신
            res = Math.max(res, dp[num]);
        }
        return dp[num];
    }
}