연속합

문제 정보

• 백준 실버 2
• DP
• 문제 링크

풀이

연속 펄스 부분 수열의 합 문제처럼 카데인 알고리즘을 사용하는 문제다.

코드

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        
        int max = arr[0]; // 전체 최대값
        int cur = arr[0]; // 현재 시점의 최대값
        for (int i = 1; i < n; i++) {
            cur = Math.max(arr[i], cur + arr[i]);
            max = Math.max(max, cur);
        }
            
       System.out.println(max);
    }
}

관련 노트

• 카데인 알고리즘