백준 / BOJ / 10211 / Maximum Subarray

문제

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.

여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max1 ≤ i ≤  j ≤ N (X[i]+...+X[j])를 구하자.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)

그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

해설

이 문제는 단순히 T*N개의 느낌으로 브루트포스로 돌려주면 T의 범위가 자연수라고만 정해져 있기 때문에 시간초과가 날 가능성이 큽니다. 따라서 입력받은 배열을 누적합한 결과를 메모리제이션 기법을 통해 저장하고 O(n^2)의 시간복잡도를 가진 이중포문을 통해 돌려주면 해결됩니다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder("");

    static int N, M;
    static int[] dp;

    static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        dp = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++)
            dp[i] = dp[i-1]+Integer.parseInt(st.nextToken());
    }

    static void process(){
        int ans = Integer.MIN_VALUE;
        for(int i=1; i<=N; i++)
            for(int j=1; j<=i; j++)
                ans = Math.max(ans, dp[i]-dp[j-1]);
        sb.append(ans).append('\n');
    }

    public static void main(String[] args) throws IOException{
        int T = Integer.parseInt(br.readLine());
        while(T-->0){
            input();
            process();
        }
        System.out.print(sb);
    }
}

 

<링크>

https://www.acmicpc.net/problem/10211