[백준] 10211 Maximum Subarray - DP JAVA

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

10211번: Maximum Subarray

코드설명

DP 문제입니다.

 

문제로직입니다.

1. dp[] : 각 index에서의 가장 큰 부분배열의 합을 의미합니다.

2. 처음에 max 값은 시작값인 arr[0] 으로 선언하고, dp[0]도 0번쨰의 부분배열의 합에서는 arr[0]이 최대입니다.

3. dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);를 통해서 이전 부분배열의 합과 현재 값을 더했을떄와 현재값만 사용할때의 최대값으로 갱신합니다.

4. max 값은 계속해서 같이 연산을 진행하며 갱신시킵니다. ( 마지막에 for문을 한번 더 도는것보다 이와같이 해야 불필요한 연산을 줄입니다. )

 

코드

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int T, N;
	public static String str = "";
	public static long[] dp = new long[5]; //최대부분배열. 
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	
    	
    	for(int t = 0; t<T;t++) {
    		st = new StringTokenizer(br.readLine());
        	N = Integer.parseInt(st.nextToken());
        	int[] arr = new int[N];
        	int[] dp = new int[N];
        	st = new StringTokenizer(br.readLine());
        	for(int i=0;i<N;i++) {
        		arr[i] = Integer.parseInt(st.nextToken());
        	}    		
        	
        	int max = arr[0];
        	dp[0] = arr[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);
    	}

    }
	
	
}