Baekjoon | Q. 1912 - 연속합

1912번: 연속합

주어진 수열에서 연속합이 가장 큰 경우를 찾는 문제이다. 연속합이란 수열에서 연속된 수를 선택해서 구할 수 있는 합이다.

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] sum = new int[n];	// i번째까지의 합을 저장하는 수열
    int[] dp = new int[n];	// i번째까지의 수열 중에서 가장 큰 연속합을 저장

    sum[0] = sc.nextInt();

    for (int i = 1; i < n; i++) {
      sum[i] = sum[i-1] + sc.nextInt();
    }

    sc.close();

    dp[0] = sum[0];
    int min = Math.min(0, dp[0]);
    
    for (int i = 1; i < n; i++) {
      int max = sum[i] - min;
      
      if(sum[i] < min) {
        min = sum[i];
      }

      dp[i] = Math.max(max, dp[i-1]);
    }

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

 풀긴 풀었는데,, 어떻게 설명해야될지 머릿속에서 정리가 안된다...

 

 sum[i]에는 0 - i번째까지의 수열의 전체 합이 저장되어 있다. 만약 sum[i]가 음수 중 최소값이고 그 이후의 sum[i+1], sum[i+2] ... 가 계속해서 양수값을 가지는 형태라면 sum[i+1]에서부터 다시 연속합을 구하는 것이 합당하다고 생각했다.(?) 내가 쓰고도 뭔말인지 모르겠다...

 

문제에 주어진 입력 예시를 통해 생각해보자.

i	0	1	2	3	4	5	6	7	8	9
arr[]	2	1	-4	3	4	-4	6	5	-5	1
sum[]	2	3	-1	2	6	2	8	13	8	9
dp[]	2	3	3	3	7	7	9	14	14	14

 i = 2일 때 전체 연속합이 -1이 나오게 되고 그 이후의 전체 연속합 중 i = 7일 때 13이 최댓값이다. i = 3, 4, 5, 6, 7일 때 최대 연속합인 sum[7] - sum[2] = 13 - ( -1 ) = 14를 가질 수 있다.

 

 dp[i]에는 i번째까지의 수열에서 최대 연속합을 저장하여 문제를 해결했다...