• 최대 부분합 (Maximum subarray problem) 문제. Kadane algorithm을 이용해서 O(n)에 해결 가능하다.

"""Solution code for "BOJ 10211. Maximum Subarray".

- Problem link: https://www.acmicpc.net/problem/10211
- Solution link: http://www.teferi.net/ps/problems/boj/10211

Tags: [DP]
"""

import sys

INF = float('inf')


def maximum_subarray(nums):
    max_sum, cur_sum = -INF, 0
    for num in nums:
        cur_sum = max(num, cur_sum + num)
        max_sum = max(max_sum, cur_sum)
    return max_sum


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())  # pylint: disable=unused-variable
        X = [int(x) for x in sys.stdin.readline().split()]
        print(maximum_subarray(X))


if __name__ == '__main__':
    main()