10-9: 연속부분 최대합 L

연속부분 최대합 L

 

문제

---

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

 

입력

---

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

출력

---

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

 

예제 입력

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

예제 출력

11

 

예제 입력

5
-1 -2 3 -2 4

예제 출력

5

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

public class dp_consecutive_sum_L {

    /** 연속부분 최대합 L

     *
     * 문제:
     * N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다.
     *
     * 입력:
     * 첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 1,000,000 ) 두 번째 줄에 n개의 정수가 주어진다.
     *
     * 출력:
     * 연속된 부분을 선택하였을 때의 최댓값을 출력한다.
     *
     * 예제 입력:
     * 8
     * 2 3 -5 8 -3 4 2 -9
     *
     * 예제 출력:
     * 11
     *
     * @param args
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[] arr = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        long[] max = new long[N];
        max[0] = arr[0];

        for (int i=1; i<N; i++){
            max[i] = Math.max(max[i-1] + arr[i], arr[i]);
//            System.out.println("max["+i+"]: " + max[i]);
        }

        long maxV = Long.MIN_VALUE;
        for (int i=0; i< N; i++){
            if (maxV < max[i]){
                maxV = max[i];
            }
        }
        System.out.println(maxV);

    }
}