[백준] 10211번 : Maximum Subarray – JAVA [자바]

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

10211번: Maximum Subarray

 

---

• 문제

 

---

• 문제 풀이

백준 10211번 Maximum Subarray는 주어진 배열에서 연속되는 부분 배열중에 가장 큰 합을 출력하는 문제다. 이 문제는 DP를 이용해서 푸는 문제인데 DP 이론이 조금 부족하면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/4 

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

 

먼저 입력으로 주어지는 배열을 int형 배열 arr에 저장했다.

 

DP 테이블을 다음과 같이 정의하겠다.

dp [i] = arr [1] + arr [2] +... + arr [i]

즉 dp [i]는 1번째 수부터 i번째 수의 합이다.

 

이 문제에서는 모든 부분 배열의 합 중에서 가장 큰 값을 구해야 하므로 이중 for-loop을 이용해 dp [n]부터 dp [i]를 빼서 최댓값을 구하는 방식으로 이 문제를 풀었다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int c = 0; c < t; c++) {
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n+1];
            int[] dp = new int[n+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            int max = Integer.MIN_VALUE;
            for (int i = 1; i <= n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                dp[i] = dp[i-1] + arr[i];
                max = Math.max(max, Math.max(arr[i],dp[i]));
            }
            for (int i = 1; i <= n; i++) {
                for (int j = n; j > i; j--) {
                    max = Math.max(max, dp[j]-dp[i]);
                }
            }
            sb.append(max + "\n");
        }
        System.out.print(sb);
    }
}

 

---

• 후기

예전에 시도했을 때는 못 풀었던 문제였는데 이번에는 풀렸다. 확실히 예전이랑 비교했을 때는 조금 더 나아진 거 같다,