[BOJ_10211] Maximum Subarray

설명

---

DP로 풀면 되는 아주 쉬운 문제입니다. 연속된 부분 수열의 합을 구해서 최대한 큰 크기의 부분 수열의 합을 구하면 됩니다. 따라서, 지속적으로 연속된 부분 수열의 최대한의 합을 구하면 됩니다. 

 

어떤 법칙이 있는 것이 아니라 예제를 보고 파악을 해보시는게 빠른 해답을 위한 길 입니다.

 

1
5
-2 1 2 3 -5

 

위와 같이 입력이 온다면 첫 번째 케이스를 빼고 [1] ~ [3] 까지의 부분 수열을 가져와서 합하면 되기 때문에 DP 반복문을 N 번 까지 체크 할 때 현재의 Max 연속된 부분 수열의 합을 지속적으로 구한다는 생각하면 됩니다.

 

코드

---

package BOJ.Dynamic_Programming;

import java.util.Scanner;

public class BOJ_10211 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            int N = scanner.nextInt();
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = scanner.nextInt();
            }
            int[] dp = new int[N];
            dp[0] = arr[0];
            int max = dp[0];
            for (int i = 1; i < N; i++) {
                dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
                max = Math.max(max, dp[i]);
            }
            System.out.println(max);
        }
    }

}

10211번: Maximum Subarray