백준 1912번 연속합 [JAVA]

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

 

 

 

한문제 한문제가 고비다..

일단 이 문제를 풀기전 한 문제를 건너뛰고 왔다. 도저히 감이 안오더라

이 문제는 그 문제보다는 쉬워보였지만 그래도 어려웠다 

 

알고리즘 설계

나는 처음에 arr이라는 배열에 값을 입력받고 dp[i]를 숫자 i개까지 포함된 상태에서 가장 큰 연속합으로 설정하였는데

이건 지금와서 보면 다이나믹프로그래밍 방법이 아니였다 그냥 for문에 지나치지 않는다 

bottom up방식으로 문제를 푼다면 i번쨰 문제를 풀떄 i-1번째 문제를 이용해서 푼다는것을 꼭 기억하자 

 

      1   2   3   4   5   6   7   8   9   10 

arr  10 -4  3    1   5   6 -35 12  21  -1

 

일단 이렇게 입력을 받았고

 

이제 dp배열을 무엇으로 정의하느냐가 가장 중요하다 

dp[i]를 arr[i]를 포함한 연속합으로 정의하면 된다 

근데 여기서는 경우의 수가 2개가 존재한다

1. 이전에 오던 연속합을 이어받아 거기다가 자기를 더한 연속합

2. 이전에 오던 연속합을 버리고 자기부터 시작하는 연속합 

이렇게 2개이다 

 

이것을 결정하는 point는

자기랑 더해서 전체 연속합이 더 작아져도 자기부터 시작하는거보다 크다면 이전에 오던 연속합을 이어받는것이다 

 

이제 이 내용을 토대로 dp배열의 값을 채워보겠다 

 

      1   2   3   4   5   6   7   8   9   10

arr  10 -4  3    1   5   6 -35 12  21  -1

dp  10  6  9    10 15 21 -14 12 33  32

 

dp[2]는 10-4 (이전에 오던 연속합을 이어 받는것) 가 -4(자기부터 시작하는것)보다 크므로 이전에 오던 연속합을 이어받는다

dp[8]은 -14+12(이전에 오던 연속합을 이어 받는것)보다 12(자기부터 시작하는것)가 크므로 자기부터 시작한다

 

이런식으로 작성한 dp값중에 가장 큰값을 출력하면 그게 연속합의 최댓값이다 

 

 

import java.util.*;

public class Main{
    public static  void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int []arr=new int[n+1];
        int []dp=new int[n+1];
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }

        dp[1]=arr[1];

        for(int i=2;i<=n;i++){
            if(dp[i-1]+arr[i]>arr[i]){
                dp[i]=dp[i-1]+arr[i]; //이전에 오던 연속합을 이어서 받는다
            }
            else{
                dp[i]=arr[i]; //자기부터 시작하는 연속합을 만든다
            }
        }

        int max=dp[1];  //여기서 무턱대고 max값을 0을 해버리면 안되는 이유는 dp값중에서 -가 있으면 다시 max값이 0이 되버리기 때문
        for(int i=2;i<=n;i++){
            if(max<dp[i])
                max=dp[i];
        }

        System.out.println(max);

    }
}