문제 이해

숫자 N과 길이 N만큼의 배열 X가 주어질 것이다.
이 때 원소의 합이 가장 큰 부분 배열을 찾아, 그 때의 부분 원소 합을 반환하는 문제이다.

문제 풀이

처음에는 두 포인터 문제로 풀기를 시도했다.
그런데 문제가 있다. 바로 배열에 음수도 들어갈 수 있다는 점이다.
즉, 특정 포인트 구간 내에 합이 작아졌을 때, 포인터를 움직인다고 해서 무조건 합이 커지는 것도 아니며 반대로 특정 포인트 구간 내에 합이 커졌을 때 구간을 줄이면 합이 작아지는 것도 아니기 때문에 포인터를 이동시키는 조건이 매우 까다롭게 된다(사실상 불가능하다)

결국 내가 생각한 방법은 DP였다.
사실 말이 좋아 DP지, 그냥 한 개씩 다 해보는 Brute-Force 방식이나 마찬가지였다.

먼저 2차원 배열을 준비한다.
그리고 dp[i][j]를 i ~ j까지의 부분 배열의 합이라고 생각했다.
그렇다면, dp[i][j] = dp[i][j-1] + dp[j][j]라고 생각하였다.
(dp[N][N] = arr[N]의 값이 저장될 것임)
그리고 값을 구할 때 항상 max에 저장된 값과 비교하여, 만약 max보다 dp[i][j]가 커진다면 max 값을 교체하는 식으로 코드를 실행시켰다.

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		int T = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for(int t=0;t<T;t++) {
			int N = sc.nextInt();
			
			// dp[i][j] : i ~ j까지의 합	
			int[] values = new int[N];
			int[][] dp = new int[N][N];
			
			int max = Integer.MIN_VALUE;
			for(int i =0;i<N;i++) {
				dp[i][i] = sc.nextInt();
				max = Math.max(max, dp[i][i]);
                // dp[i][i]는 배열 X의 i번째 원소 값이 저장 될 것이다.
                // X[i]도 엄연한 부분 배열이기 때문에 max값과 비교가 필요하다
			}
			
			for(int i =0;i<N-1;i++) {
				for(int j =i+1;j<N;j++) {
                     // dp[i][j]를 구하는 방법. 
                    // 이후 max값과 비교하여 큰 값을 선택
					dp[i][j] = dp[i][j-1] + dp[j][j];
					max = Math.max(max, dp[i][j]);
				}
			}
			
			sb.append(max).append("\n");
		}
		System.out.println(sb);
	}
	
	
	static class FastReader // 빠른 입력을 위한 클래스
}

결과