[백준 1912번 : 연속합] java 풀이

백준 1912번 : 연속합 바로가기
연속적인 합의 크기를 구하는 문제이므로 dp 배열에 연속합의 결과를 담아야한다.

• 우선 arr 배열에 임의의 수열을 저장한다.
• dp 배열에 인덱스 n까지의 합을 저장한다.
• 이 때 (인덱스 n-1까지의 합) + arr[n] 과 arr[n] 중 큰 값을 dp에 저장한다.
• 즉 이전까지의 합과 현재 배열 값을 더했을 때 max 값이 되면 이 값을 dp 배열에 저장하고, 더하지 않고 그냥 현재 배열 값이 더 클 경우는 dp 배열이 현재 arr 배열 값으로 초기화된다고 생각하면 된다.
• 이전까지의 합과 현재 배열 값을 더했을 경우가 현재 배열 값보다 작아진다는 것은 현재 배열 값이 음수인 경우 등... 일 것이다.

점화식을 if문으로 표현하면,
if(dp[i-1]+arr[i]>=arr[i])
dp[i]=dp[i-1]+arr[i];
else
dp[i]=arr[i];

🔑 java 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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());
        }
        int dp[]=new int[n];
        dp[0]=arr[0];
        int max=dp[0];
        for(int i=1; i<n; i++){
            if(dp[i-1]+arr[i]>=arr[i])
                dp[i]=dp[i-1]+arr[i];
            else
                dp[i]=arr[i];
            if(max<=dp[i])
                max=dp[i];
        }
        System.out.println(max);
    }
}