코드트리 [자바 java] 연속 부분 합의 최댓값 구하기

https://www.codetree.ai/missions/2/problems/max-of-partial-sum?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 연속된 수들의 합의 최댓값을 구하는 문제이다. dp문제 중에는 현재 탐색하는 지점의 앞에 있는 값을 모두 탐색해야 하는 경우도 많은데, 이 문제는 연속된 값을 구하는 문제이므로 바로 앞 dp값만 계산하면 된다.

 

dp[i]의 값은 앞서 계속 더해왔던 값의 최댓값과 arr[i]를 단독으로 사용했을 때의 값을 비교한 값 중 더 큰 값을 의미한다.

dp값 중에서 dp[n]이 가장 큰 값은 아니므로 (ex)arr[n]이 음수이면 이를 포함하지 않은 값이 더 크다.) dp중에서 가장 큰 값이 답이 된다.

 

나는 이 값을 처음에 0으로 설정했었는데, arr값이 음수가 나올 수 도 있으므로 값 비교가 제대로 이루어지지 않았었다. 또한 integer.min_value를 사용해봤는데, 이는 배열 값이 1개일 때 오류가 나왔다. 앞으로는 초기값 설정에 주의해야겠다.

 

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


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];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        //dp에 점화식 넣기 앞의 dp값보다 현재 자신의 값이 크면 그걸 dp에 넣는다.


        int[] dp = new int[n];

        int ans = arr[0];

        dp[0] = arr[0];

        for(int i = 1;i<n;i++){
            dp[i] = Math.max(arr[i], dp[i-1] + arr[i]);
            ans = Math.max(ans, dp[i]); // 답은 dp중 가장 큰 값
        }

         System.out.println(ans);

    }
}