[백준저지] 1912번 : 연속합

www.acmicpc.net/problem/1912

1912번: 연속합

1. 문제

n개의 정수로 이루어진 임의의 수열이 주어지는데, 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제.

 

2. 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N+1];
        int[] D = new int[N+1];
        for (int i = 1; i <= N; i++) {
            A[i] = sc.nextInt();
        }
        for (int i = 1; i <= N; i++) {
            if (i == 1) {
                D[i] = A[i];
                continue;
            }
            int l = D[i-1] + A[i];
            if (l > A[i]) {
                D[i] = l;
            } else {
                D[i] = A[i];
            }
        }
        int result = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++) {
            if (D[i] > result) {
                result = D[i];
            }
        }
        System.out.println(result);
    }
}

D[i] = i번째 수로 끝나는 가장 큰 연속합

D[i] = max(D[i-1]+A[i], A[i])

배열을 한번 loop하면서 연속할 지, 새로 시작할 지 값을 비교후 D 배열에 결과값을 저장.