[백준 1912, Java] 연속합

문제

www.acmicpc.net/problem/1912

1912번: 연속합

 

풀이

• 브루트포스로 푼다면, 주어진 수열을 순회하면서 해당 인덱스의 숫자를 선택한다, 선택하지 않는다로 풀 수 있다. 각 인덱스의 숫자를 선택하고서 선택된 숫자의 합을 ArrayList에 add한다. 문제에서 수는 한개 이상 선택해야한다고 했으므로 ArrayList에 맨 마지막에 add되는 숫자는 remove한다. 그런데 이렇게 풀게 될 경우 시간복잡도는 2의 N(수열 원소의 갯수) 인데, N의 최댓값은 100,000이므로 시간초과가 난다. 따라서 브루트 포스로 풀 경우 시간초과가 난다

• 따라서 이 문제는 브루트 포스가 아닌 다른 방법으로 풀어야 한다. 

• 문제에서 "연속된 수열의 합" 이라고 했으니 numArray[index] 까지의 연속합 중 최대는 numArray[index-1]까지의 최댓값과 연관지어서 생각할 수 있다. 

• 점화식으로 나타내면 f(n) = numArray의 n까지의 연속합 중 최대 라고 정의할 수 있다. 따라서 f(n) = Max(f(n-1+ numArray[n], numArray[n])으로 나타낼 수 있다. numArray[n]이 음수인 경우 f(n-1)+ numArray[n] 보다  f(n-1)이 더 크고, numArray[n]이 양수인 경우 f(n-1)+numArray[n]이 numArray[n]보다 크다. 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] numArray;
    public static int[] memo;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        numArray = new int[N];
        // memo[index] = numArray의 index까지 연속합 중 최대 연속합
        // memo[index] = Max(memo[index-1]+numArray[index], numArray[index]])
        memo = new int[N];

        st = new StringTokenizer(br.readLine()," ");
        for(int index = 0; index<N; index++){
            numArray[index] = Integer.parseInt(st.nextToken());
        }

        calculateMaxSum();
        int result = getMaxSum();
        bw.write(String.valueOf(result));
        bw.flush();

    }
    public static void calculateMaxSum(){
        memo[0] = numArray[0];
        for(int index = 1 ; index<N ; index++){
            memo[index] = numArray[index];
            int seqSum = memo[index-1] + numArray[index];
            if(seqSum>memo[index]) memo[index] = seqSum;
        }
    }

    public static int getMaxSum(){
        int maxSum = memo[0];
        for(int index = 1; index<N; index++){
            if(memo[index]>maxSum) maxSum =  memo[index];
        }
        return maxSum;
    }
}