[AJ/DP] 연속 부분 최대합 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

예제 출력

copy

5

---

풀이

data 배열에는 i 까지의 Max값을 구해서 저장한다.

즉 data[3] 을 구할 때, data[2]는 i=2일 때의 최대값이 들어가 있기 때문에 현재 입력받은 value 값과 그 값을 data[2]와 더했을 때 더 큰 값을 저장하면 data[3]에는 i=3일 때 최대값이 들어가게 된다. 

코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int data[]= new int[n];
        
        int max = -1;
        for(int i=0;i<n;i++) {
            int value =sc.nextInt();
            if(i==0)
                data[i] = value;
            else {
                data[i] = Math.max(value, value+data[i-1]);
            }
            if(max<data[i])
                max = data[i];
        }
        System.out.println(max);
    }

}