문제
풀이
부분집합을 모두 고려하면 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)}")