사용자 도구

사이트 도구


ps:problems:boj:10211

Maximum Subarray

ps
링크acmicpc.net/…
출처BOJ
문제 번호10211
문제명Maximum Subarray
레벨실버 3
분류

DP

시간복잡도O(T*n)
인풋사이즈T<=?, n<=1000
사용한 언어Python
제출기록30840KB / 76ms
최고기록64ms
해결날짜2022/05/29
태그

[라이] 구간합 배열

풀이

코드

"""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()

토론

댓글을 입력하세요:
U B A O H
 
ps/problems/boj/10211.txt · 마지막으로 수정됨: 2022/05/31 14:24 저자 teferi