[SW Academy] 5642. 합

문제

풀이

부분집합을 모두 고려하면 O(n^2)이므로 시간초과가 뜬다.
즉, 동적계획법인 카데인 알고리즘을 이용하여 해결하면 되는 문제.
그럼 시간복잡도가 O(n)이 된다.

카데인 알고리즘

t = int(input())
for test_case in range(t):
    n = int(input())
    nums = list(map(int, input().split()))

    dp = [0] * n
    temp = []

    dp[0] = nums[0]
    for i in range(1, n):
        dp[i] = max(nums[i], nums[i] + dp[i-1])
    temp.append(max(dp))

    print(f"#{test_case + 1} {max(temp)}")