[백준] 1912.연속합

[문제 바로가기](""" https://www.acmicpc.net/problem/1912 """)

문제 풀이

두 번의 for문을 사용 -> 시간 초과 발생, 보통 부분합은 dp를 이용한다

정답 코드

"""
https://www.acmicpc.net/problem/1912
"""
N=int(input())
nums = list(map(int,input().split()))

dp = [0]*N
dp[0] = nums[0]

for i in range(1,N):
    # 여기까지 모두 더한 값이랑 현재 값을 비교, 현재까지 더한 값이 더 작으면 앞의 값을 사용할 이유가 없음
    # 현재값부터 dp[i]에 다시 저장
    dp[i] = max(nums[i],dp[i-1] + nums[i])

print(max(dp))

추가적인 개념

dp에 대한 이해가 중요함
앞의 값을 더하지 않고 다시 수열을 시작하는 기준이 어떻게 되는지 파악할 것 -> 이 문제의 경우엔 현재까지 더한 값이 현재 값보다 작다면 굳이 앞의 값을 사용할 이유가 없으므로 해당 위치부터 다시 수열을 시작한다.