BOJ - 10211 ) Maximum Subarray

---

www.acmicpc.net/problem/10211

10211번: Maximum Subarray

 

---

수열에서 연속된 부분배열의 최댓값을 구하는 문제..

 

양수면 계속더하면 최댓값이 되지만 중간에 음수가있는경우,

 

음수의 덧셈으로 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);
	}

}

---