[Silver IV] Maximum Subarray - 10211

문제 링크

성능 요약

메모리: 2028 KB, 시간: 0 ms
메모리: 15400 KB, 시간: 164 ms

분류

브루트포스 알고리즘, 다이나믹 프로그래밍, 누적 합

제출 일자

2024년 2월 22일 14:12:10

문제 설명

크기 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보다 작은 정수이다.

출력

각 테스트케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

문제 풀이

• arr에 값을 차례대로 입력받는다.
• dp 배열에 누적합이 0보다 작은 경우엔 0을 받도록 하고 arr 배열 값을 더해준다.
• max_result에 가장 큰 값을 넣어준다.