[백준/boj] 10211: Maximum Subarray (Java) / 분할 정복 / DP

문제

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

10211번: Maximum Subarray

풀이

1. 분할 정복(이분 탐색) 풀이

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

public class Main_BOJ_10211_MaximumSubarray {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int T;
	static int N;
	static int[] X;
	static int maxNum = Integer.MIN_VALUE;

	public static void main(String[] args) throws Exception {
		T = stoi(br.readLine());

		for (int t = 1; t <= T; t++) {
			N = stoi(br.readLine());
			X = new int[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				X[i] = stoi(st.nextToken());
			}
			maxNum = Integer.MIN_VALUE;
			maxNum = getMaxSubArr(0, N);
			bw.append(maxNum + "\n");
		}
		bw.flush();
		bw.close();
	}

	private static int getMaxSubArr(int start, int end) {
		if (start == end-1) {
			return X[start];
		}
		int mid = (start + end) / 2;
		int sum = 0;
		int maxL = X[mid-1];
		int maxR = X[mid];
		for (int i = mid-1; i >= start; i--) {
			sum += X[i];
			maxL = Math.max(sum, maxL);
		}

		sum =0;
		for (int j = mid; j < end; j++) {
			sum += X[j];
			maxR = Math.max(maxR, sum);
		}

		int L = getMaxSubArr(start, mid);
		int R = getMaxSubArr(mid, end);
		return Math.max(L > R ? L : R, maxL + maxR);
	}

	private static int stoi(String input) {
		return Integer.parseInt(input);
	}

 

2. DP 풀이

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

public class Main {
	static int N;
	static int[] list, dp;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			list = new int[N+1];
			dp = new int[N+1];
			st = new StringTokenizer(br.readLine());
			for(int i=1; i<= N; i++) {
				list[i] = Integer.parseInt(st.nextToken());
			}
			
			System.out.println(getMaxArraySum(N));
		}
		
		
	}
	private static int getMaxArraySum(int n) {
		int answer = Integer.MIN_VALUE;
		for(int i=1; i<= n; i++) {
			dp[i] = Math.max(list[i], dp[i-1] + list[i]);
			answer = Math.max(answer, dp[i]);
		}
		return answer;
	}
}