백준(BOJ) 1912 : 연속합 (JAVA)

문제링크 : https://www.acmicpc.net/problem/1912

1912번: 연속합

이 문제를 보고 '그냥 모든 경우의 수를 다 구하면 안 되나?'란 생각이 들었다. 이 때의 시간 복잡도는 O(n^2)인데 n의 최댓값이 100,000이라 이 정도면 가능하지 싶었다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int[] seq = new int[n];
        int[] sums = new int[n];
        int max = Integer.MIN_VALUE;
        int sum = 0;
        
        for(int i = 0; i < n; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
            sum += seq[i];
            sums[i] = sum;
            
            if(max < sums[i]) {
                max = sums[i];
            } 
        }
        
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                int tmp = sums[i] - sums[j];
                
                if(max < tmp) {
                    max = tmp;
                }
            }
        }
        
        System.out.println(max);
    }
}
 

 

맞긴 맞았는데 상위권 풀이와 비교해보니 시간 차이가 너무 많이났다-_- 이거이거 잘못 풀었구나...ㅠㅠ

 

제대로 푼 방법에 대한 설명을 하겠다. 0부터 n - 1까지 i를 증가시키면서 그 시점에서의 최댓값을 구한다. 그 시점에서의 최댓값이란, i = a라고할 때, 0부터 a까지의 수열 중에서 a가 선택되었을 때의 가장 큰 연속합을 의미한다. 아래의 수열을 예를 들어 설명해보겠다.

 

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

 

i=0일 때 -> 10

i=1일 때 -> i=0일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 6

i=2일 때 -> i=1일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 9

i=3일 때 -> i=2일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 10

i=4일 때 -> i=3일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 15

i=5일 때 -> i=4일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 21

i=6일 때 -> i=5일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> -14

i=7일 때 -> i=6일때의 최댓값이 음수이므로 더하지 않는 것이 최대값 -> 12

i=8일 때 -> i=7일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 33

i=9일 때 -> i=8일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 32

 

따라서 최댓값이 33임을 알 수 있다. 이 때의 시간 복잡도는 O(n)이다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int[] seq = new int[n];
        seq[0] = Integer.parseInt(st.nextToken());
        int maxCandidate = seq[0];
        int max = maxCandidate;
        
        for(int i = 1; i < n; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
            
            if(maxCandidate > 0) {
                maxCandidate = seq[i] + maxCandidate;
            } else {
                maxCandidate = seq[i];
            }
            
            if(max < maxCandidate) {
                max = maxCandidate;
            }
        }
        
        System.out.println(max);
    }
}