[백준 10211] Maximum Subarray

 

1차원 구간합 배열을 만들어 완전탐색으로 매 구간합의 최대값을 구한다.

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int t = Integer.parseInt(br.readLine());
        while(t-->0) {
            int n = Integer.parseInt(br.readLine());
            int psum[] = new int[n+1];
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) {
                int num = Integer.parseInt(st.nextToken());
                psum[i+1] = psum[i] + num;
            }
            
            int max = Integer.MIN_VALUE;
            for(int i=1; i<=n; i++)
                for(int j=i; j<=n; j++)
                    max = Math.max(max, psum[j] - psum[i-1]);
            System.out.println(max);
        }
    }
}