백준 1912 / 연속합

문제

풀이

설명

n개의 정수로 이루어진 임의의 수열이 주어진다.
이중 연속된 몇개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구한다.

A[i] = 실제로 입력받는 수가 들어간다.
D[i] = i번째에서 끝나는 연속합의 최대값이 들어간다.

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

시간복잡도 : O(n)

코드

import java.util.Scanner;

public class Num1912 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
        int n = sc.nextInt();
        int[] a = new int[n];
        
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        
        int[] d = new int[n];
        
        for (int i=0; i<n; i++) {
            d[i] = a[i];
            if (i == 0) {
                continue;
            }
            if (d[i] < d[i-1] + a[i]) {
                d[i] = d[i-1] + a[i];
            }
        }
        
        int ans = d[0];
        
        for (int i=0; i<n; i++) {
            if (ans < d[i]) {
                ans = d[i];
            }
        }
        System.out.println(ans);
		
	}

}

코드설명

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