[백준] 1912 연속합

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

 

접근 방법

문제에서 연속된 수의 개수를 정해주지 않았기 때문에 연속된 임의의 개수의 수 합 데이터를 계속해서 보존해야 한다고 생각하였다. 이를 표로 나타내면 아래와 같다.

 

10	-4	3	1	5	6	-35	12	21	-1
6	-1	4	6	11	-29	-23	33	20
9	0	9	12	-24	-17	-2	32
.
.
.
.
.
.
18

하지만 이 알고리즘을 제출했을 때 메모리 초과가 발생하였다. 

 

메모리 초과가 발생했기 때문에 배열을 2차원이 아니라 1차원 배열을 사용해서 풀 수 있는 문제라는 것을 짐작할 수 있었지만 결국 해결하지 못해 다른 분이 작성한 알고리즘을 참고하였다.

 

해당 알고리즘은 근본적으로 나와 동일하지만 모든 값을 보존하지 않는다는 점에서 큰 차이를 보인다.

 

처음 원소에서 부터 계속 원소를 누적해서 더해가되 누적된 합이 현재 값보다 클 경우 값을 보존하고 그렇지 않을 경우에는 누적된 값이 현재 값 보다 작기 때문에 그 합을 현재 값으로 변경한다.

 

초기 작성 소스 코드

import java.util.*;

public class Main{
public static void main(String[] args) {
		 Scanner scanner = new Scanner(System.in);
		 
		 int n = Integer.valueOf(scanner.nextLine());
		 int[][]d = new int[n][n];
		 int max = Integer.MIN_VALUE;
         String[] line = scanner.nextLine().split(" ");
		 
		 for(int i=0;i<n;i++) {
			 d[0][i] = Integer.valueOf(line[i]);
		     max = Math.max(max, d[0][i]);
         }
		 
		 
		 for(int i=1;i<n;i++) {
			 for(int j=0;j<n;j++) {
                d[i][j] = Integer.MIN_VALUE;
			 }
		 }
		 
		 for(int step=1;step<n;step++) {
			 for(int i=0;i<n-step;i++) {
				 d[step][i] = d[step-1][i] + d[0][i+step];
				 max = Math.max(max, d[step][i]);
			 }
		 }
		 System.out.println(max);
	}
    }

제출 소스 코드

import java.util.*;
public class Main{
public static void main(String[] args) {
		 Scanner scanner = new Scanner(System.in);
		 
		 int n = Integer.valueOf(scanner.nextLine());
		 int[] d = new int[n];
         String[] line = scanner.nextLine().split(" ");
		 
		 for(int i=0;i<n;i++) {
			 d[i] = Integer.valueOf(line[i]);
         }
         int value = d[0];
		 int max = value;
		 for(int i=1;i<n;i++){
             value = Math.max(d[i], d[i] + value);
             max = Math.max(max, value);
         }
		 System.out.println(max);
	}
}