[BOJ] 백준 1912 연속합

출처:  https://www.acmicpc.net/problem/1912

 Input 

10

10 -4 3 1 5 6 -35 12 21 -1

 

 Output 

3

배열의 연속된 부분합을 구하는 문제입니다.

① 중첩 for문을 이용하면 시간초과.

② 모든 원소가 음수일 때, 결과는 『0』이 아닙니다.

 Input 

1

-100

 

 Output 

-100

구현

DP 적용해서 부분문제부터 해결

시뮬레이션]

---

import java.util.Scanner;
 
public class Main {
     
    static final int MIN = Integer.MIN_VALUE;
     
    public static void main(String[] args) {
         
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
         
        int[] arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(sc.next());
        }
         
        int temp = 0;
        int answer = MIN;
        for(int i=0; i<N; i++) {
            temp = Math.max(temp, 0) + arr[i];
            answer = Math.max(answer, temp);
        }
         
        System.out.println(answer);
    }
}