백준 13398 연속합2 파이썬 Python py (재귀 풀이)

13398번 풀이를 블로그에 찾아보니, 대부분 반복문 DP 풀이만 나오는데 나는 개인적으로 재귀 DP 가 더 편해서 재귀로 풀어 보았다. 

import sys

sys.setrecursionlimit(10**6)

N = int(input())

arr = list(map(int, input().split()))

dp = [[float('-inf')] * 2 for _ in range(len(arr))]


def solve(i, c):

    if dp[i][c] != float('-inf'):
        return dp[i][c]
    
    if i == 0:
        if c == 0:
            dp[i][c] = arr[i]
            return dp[i][c]
        else:
            dp[i][c] = float('-inf')
            return dp[i][c]

    if c == 0:
        dp[i][c] = max(solve(i-1, 0) + arr[i], arr[i])

    if c == 1:
        dp[i][c] = max(solve(i-1, 1) + arr[i], solve(i-1, 0))

    return dp[i][c]


maxSum = float('-inf')
solve(N-1, 0)
solve(N-1, 1)

for i in range(len(arr)):
    tempMax = max(dp[i][0], dp[i][1])
    maxSum = max(tempMax, maxSum)


print(maxSum)​