백준 1912번
https://www.acmicpc.net/problem/1912

문제

---

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

생각하기

---

• 연속적으로 증가하는 숫자를 찾는 것이 아닌, 그냥 배열에서 연결된 순으로 연속적인 숫자의 합 중 가장 큰 수를 찾는 문제이다.

• 무작정 앞에 나열된 값의 합을 찾는 것이 아닌, 지속적인 비교가 필요함

테스트케이스로 쉽게 설명하자면

memo[6]에서 memo[7]로 넘어가는 부분이 이해하기 쉬울 것 같다

10
10 -4 3 1 5 6 -35 12 21 -1

수열에서 10부터 시작해서 -35까지 연결된 수의 합은 -14라는 값을 가지게 된다.
이 값이 해당 연속으로 온 숫자 중에 가장 큰 값이 되는데,

-14+12인 2와 12라는 숫자를 비교했을 때, 12라는 숫자가 더 크기때문에 여기서 연속된 수가 끊기고 12부터 새로운 연속이 시작된다.

이제 12, 21, -1 3개의 숫자 중 모두 더했을 때 가장 큰 조합은 당연히 12 + 21이 된다.

해당 방식을 통해서 memo 배열을 채우게 되는 것이다.

동작

		memo[0] = arr[0];
		max = arr[0];
		
		DP(N-1);

가장 앞의 숫자는 연결되지 않았기 때문에 당연히 가장 작은 숫자가 됨

DP메소드의 재귀는 Top-Down 방식으로 가장 위에서 부터 출발함.

코드

---

Java

import java.util.*;
import java.io.*;

public class Main {
	static Integer memo[];
	static int arr[];
	static int max;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		arr = new int[N];
		memo = new Integer[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		memo[0] = arr[0];
		max = arr[0];
		
		DP(N-1);

		System.out.println(max);
	} // End of main
	
	private static int DP(int N) {
		
		if(memo[N] == null) {
			memo[N] = Math.max(DP(N-1) + arr[N], arr[N]);
			
			max = Math.max(memo[N], max);
		}
		
		return memo[N];
	} // End of DP
} // End of Main class

Kotlin

Top-Down

import java.util.*
import java.io.*

private lateinit var arr : IntArray
private lateinit var memo : IntArray
private const val min = Integer.MIN_VALUE;
private var max = 0

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )

    var N = br.readLine().toInt()
    arr = IntArray(N);
    memo = IntArray(N, {min})

    val st = StringTokenizer(br.readLine())
    for(i in 0 until N) {
        arr[i] = st.nextToken().toInt()
    }

    memo[0] = arr[0]
    max = arr[0]

    DP(N-1)
    print(max)
} // End of main

private fun DP(N : Int) : Int{

    if(memo[N] == min) {
        memo[N] = Math.max(DP(N-1) + arr[N], arr[N])

        max = Math.max(memo[N], max);
    }

    return memo[N];
} // End of DP

Bottom-Up

import java.util.*
import java.io.*
private lateinit var arr : IntArray
private lateinit var memo : IntArray
fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )

    var N = br.readLine().toInt()
    arr = IntArray(N)
    memo = IntArray(N)

    val st = StringTokenizer(br.readLine())
    for(i in 0 until N) arr[i] = st.nextToken().toInt()

    memo[0] = arr[0]
    var max = arr[0]

    for(i in 1 until N) {
        memo[i] = Math.max(memo[i-1] + arr[i], arr[i])

        max = Math.max(max, memo[i])
    }

    print(max)
} // End of main