연속합

풀이

 나는 이 문제를 누적합 알고리즘을 응용해서 풀었다. 입력값 배열 arr이 주어졌을 때 누적합 배열 pSum을 구하자. 문제에서 구하고자 하는 바가 최대의 구간합이므로 pSum[i]-pSum[j]의 최대값을 구하면 된다(i>j). 아래 예제에서는 19-(-14)=33이 정답이 된다.

arr[] : 10 -4 3 1 5 6 -35 12 21 -1
pSum[] : 10 6 9 10 15 21 -14 -2 19 18

시간 복잡도 : O(N)

Java

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 누적합 배열 구하기
        int[] pSum = new int[n+1];
        for(int i=1; i<n+1; i++){
            int x = Integer.parseInt(st.nextToken());
            pSum[i] = pSum[i-1]+x;
        }

        int min_value = 0;
        int max_value = Integer.MIN_VALUE;
        for(int i=1; i<n+1; i++){
            max_value = Math.max(max_value, pSum[i]-min_value);
            if(min_value>pSum[i]){
                min_value = pSum[i];
            }
        }

        bw.write(String.valueOf(max_value));
        bw.flush();
        bw.close();
        br.close();
    }
}