연속부분의 최대 합

연속부분 최대합 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.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static int result = Integer.MIN_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b[];

        a = sc.nextInt();
        b = new int[a];

        for (int i = 0; i < a; i++) {
            b[i] = sc.nextInt();

            if (i > 0 && b[i - 1] + b[i] > b[i]) b[i] += b[i - 1];

            if (b[i] > result) result = b[i];
        }

        System.out.println(result);

    }
}