[백준 1912] 연속합

 

수열의 크기와 같은 크기의 dp 배열을 만들어 각 인덱스별로 최대값을 저장한다.

 

수열의 값 중 적어도 한 개를 선택해야 하고 연속적으로 사용해야 하므로,

이전 dp의 최대값 + 현재 배열의 값 / 현재 배열의 값을 비교하여 큰 것을 사용하면 된다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[] = new int[n];
        int dp[] = new int[n];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        dp[0] = a[0];
        int max = dp[0];
        for(int i=1; i<n; i++) {
            dp[i] = max(dp[i-1] + a[i], a[i]);
            max = max(max, dp[i]);
        }
        System.out.println(max);
    }
    
    public static int max(int a, int b) {
        return a > b ? a : b;
    }
}