🔗 Problem

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

👩‍💻 Code

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

// 연속합

public class BJ1912 {

	static int n;
	static int[] arr;
	static int[] dp;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		dp = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0] = arr[0];
		for(int i = 1; i < n; i++) {
			dp[i] = Integer.max(dp[i-1] + arr[i], arr[i]);
		}
		
		Arrays.sort(dp);
		System.out.println(dp[dp.length - 1]);
	}
}

📌 Note

아이디어

• max( dp[i-1] + arr[i] , arr[i] ) : 이전 max 값에 i번째를 더한 것(연속)과 i번째부터 새로 시작하는 것(연속 중단)을 비교하여 dp에 담았다.
• dp[] 중 가장 큰 값을 출력

메모리 초과

• 처음에 dp[][] 2차원 배열로 선언하여 메모리 초과가 발생했다.
• n == 100,000 인 최악의 경우,
  100,000 x 100,000 x 4 = 40,000,000,000 Byte = 10,000 MB
  위와 같은 메모리를 차지해야 하므로 문제가 된다.
• 꼼꼼하게 풀자 ~