알고리즘/Dynamic Programming
BOJ - 10211 ) Maximum Subarray
개발자가될수있을까?
2020. 11. 16. 22:57
10211번: Maximum Subarray
크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있
www.acmicpc.net
수열에서 연속된 부분배열의 최댓값을 구하는 문제..
양수면 계속더하면 최댓값이 되지만 중간에 음수가있는경우,
음수의 덧셈으로 0보다 크면 계속 더해준다. N^2 / NlogN의 풀이도 있지만,
O(N)에 해결가능하다
package algorithm;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class MaximumSubarray {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(st.nextToken());
for(int i=0 ; i < n ; i++) {
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
int num[] = new int[t];
st = new StringTokenizer(br.readLine());
for(int ii=0;ii<t;ii++) {
num[ii] = Integer.parseInt(st.nextToken());
}
int answer = -987654321;
int dp[] = new int[t];
dp[0] = num[0];
for(int ii=1 ; ii<t; ii++) {
dp[ii] = Math.max(dp[ii-1], 0) + num[ii];
answer = answer > dp[ii] ? answer : dp[ii];
}
answer = answer > dp[0] ? answer : dp[0];
sb.append(answer+"\n");
}System.out.println(sb);
}
}
