DP 정복 - 4.2 다이내믹 프로그래밍을 사용한 문제 해결 : 예제 풀기 3

오늘은 평소에 좀 자주 봤었던 '연속된 부분 배열의 최댓값 구하기' 다.

알고리즘 문제풀이에서는 보통 '연속 부분 최대합'이라고도 하는 문제다.

 

BOJ에는 다행히 문제가 존재한다. (아래 링크 참조)

https://www.acmicpc.net/problem/1912

 

가장 간단하게 풀 수 있는 방법은

첫 인덱스(i)부터 시작해서 마지막 인덱스(n)까지 순회하되,

  내부의 인덱스(j = i)에서 마지막 인덱스(n)까지 순회하며 더한 값 중 가장 큰 값을 구하면 된다.

그러면 2중 for statement를 사용하게 되니 O(n^2)의 시간 복잡도를 갖게 된다.

소스는 다음과 같다.

def solve(n, ar):
    res = -100000000

    for i in range(n):
        temp = 0
        for j in range(i, n):
            temp += ar[j]
            if temp > res:
                res = temp

    return res


if __name__ == '__main__':
    n = int(input())
    ar = list(map(int, input().split()))
    print(solve(n, ar))

당연히 BOJ에 제출하면 시간 초과. n의 최댓값이 100,000이므로 n^2 = 10,000,000,000 이 되므로 시간 초과가 될 수밖에 없다.

 

이 문제를 선형 시간(O(n))의 시간 복잡도로 풀어본다. 배열을 딱 한 번만 뒤지는 이 알고리즘은 카데인 알고리즘이라고 부른다. 두 개의 정수형 변수를 사용한다.

카데인 알고리즘으로 작성한 코드는 다음과 같다.

def solve_kadane(n, ar):
    res = -100000000
    temp = 0
    neg_max = -100000000
    neg_cnt = 0

    for i in range(n):
        temp += ar[i]

        if neg_max < ar[i]:
            neg_max = ar[i]

        if ar[i] < 0:
            neg_cnt += 1

        if temp < 0:
            temp = 0

        if res < temp:
            res = temp

    return neg_max if neg_cnt == n else res


if __name__ == '__main__':
    n = int(input())
    ar = list(map(int, input().split()))
    print(solve_kadane(n, ar))

책에는 전부 음수인 경우에 대해서는 구현이 되어있지 않아서

내 맘대로 수정(혹은 추가) 해 봤다. 다행히 BOJ에서는 통과!

 

다음으로는 이번 절 말미에 나와있는 DP의 점화식을 활용해 소스를 작성해봤다.

def solve_dp(n, ar):
    dp = [0 for _ in range(n)]
    dp[0] = ar[0]

    for i in range(1, n):
        dp[i] = max(dp[i - 1] + ar[i], ar[i])

    return max(dp)


if __name__ == '__main__':
    n = int(input())
    ar = list(map(int, input().split()))
    print(solve_dp(n, ar))

예전에 한 번 풀어봤던 문제라 그런지 첫 접근이 어렵지는 않았다. 

그럼에도 불구하고 O(n^2)에서 O(n)으로 바꿀 때는 꽤 생각할 거리가 많았다는 게 함정.