[실전 문제] 연속 부분 최대합 L

1. 문제

N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다.

---

입력

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 1,000,000 ) 두 번째 줄에 n개의 정수가 주어진다. 

출력

연속된 부분을 선택하였을 때의 최댓값을 출력한다.

예제 입력

case 1)

8
2 3 -5 8 -3 4 2 -9

 

case 2)

5
-1 -2 3 -2 4

예제 출력

case 1) 11

case 2) 5

 

 

 

2. 풀이

이 문제의 점화식은 다음과 같다.

• T(i) = max(T(i-1) + Data(i), Data(i))

 

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            int value = Integer.parseInt(st.nextToken());
            if(i == 0) {
                arr[i] = value;
            }
            else {
                if(value < arr[i-1] + value) arr[i] = arr[i-1] + value;
                else arr[i] = value;
            }
        }
        
        int max = -987987987;
        for(int i = 0; i < n; i++) {
            if(max < arr[i]) max = arr[i];
        }
        
        bw.write(max + "");

        br.close();
        bw.flush();
        bw.close();
    }
}