BOJ 백준 1912: 연속합

Table of contents

들어가며

이 문제는 DP라는 걸 아는 순간 매우 쉬워집니다. N이 최대 10만이어서, N^2안에는 통과가 안되고, 이 시간 복잡도를 어떻게 줄이느냐의 싸움입니다.

풀이과정

AC 받은 Python 코드

import sys

input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input().rstrip())
    nums = [*map(int, input().rstrip().split())]
    lenNums = len(nums)
    dp = [0 for _ in range(lenNums)]
    dp[0] = nums[0]
    for i in range(1, lenNums):
        dp[i] = max(dp[i - 1] + nums[i], nums[i])

    print(max(dp))