10211번. Maximum Subarray

 

아이디어

dp[i] 를 i 번째 숫자를 마지막으로 하는 최대부분배열의 합이라고 정의한다면 다음과 같은 점화식을 세울 수 있다.

 

dp[i] = Math.max(dp[i - 1], 0) + numbers[i]

 

i - 1 번째 숫자를 마지막으로 하는 최대부분배열의 합이 음수라면 i 번째 숫자만으로 이루어진 배열이 i 번째 숫자를 마지막으로 하는 최대부분배열이 되기 때문이다.

 

 

풀이코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());

            int[] numbers = new int[N + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                numbers[i] = Integer.parseInt(st.nextToken());
            }

            int[] dp = new int[N + 1];
            int result = Integer.MIN_VALUE;
            for (int i = 1; i <= N; i++) {
                dp[i] = Math.max(dp[i - 1], 0) + numbers[i];
                result = Math.max(result, dp[i]);
            }

            sb.append(result).append("\n");
        }

        System.out.println(sb);
    }
}