BOJ 1912. 연속합

BOJ 1912. 연속합

풀이

d[i] = n개의 정수로 이루어진 임의의 수열 에서 i로 끝나는 연속합(연속된 몇 개의 수를 선택해서 구할 수 있는 값 중 가장 큰 값)

임의의 수열에서 i로 끝나는 경우는 2가지가 있다
1. i-1번째와 i번째가 연속하는 경우 -> d[i-1]+arr[i]
2.i-1번째와 i번째가 연속하지 않는 경우 -> arr[i]

점화식
d[i] = max(arr[i], arr[i] + d[i-1])

import java.io.IOException;
import java.util.Scanner;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] d = new int[n];
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        sc.close();

        d[0] = arr[0];

        for (int i = 1; i < n; i++) d[i] = Math.max(arr[i] + d[i - 1], arr[i]);

        int max = -1001;
        for (int i = 0; i < n; i++) {
            if (max < d[i]) {
                max = d[i];
            }
        }
        System.out.println(max);
    }
}

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val arr = readLine()!!.split(" ").map { it.toInt() }
    val d = IntArray(n)

    d[0] = arr[0]
    for (i in 1 until n) d[i] = max(arr[i] + d[i - 1], arr[i])
    println(d.maxOf { it })
}

풀이소스

github.com/beomjo/algorithm-study/commit/201d262b42354a89703765813faec885f4e7c603