문제 설명
•
크기가 인 수열에 대해 연속된 수 들의 합 중에서 가장 큰 값을 구하는 문제
예제 입력/출력
•
입력1
10
10 -4 3 1 5 6 -35 12 21 -1
Plain Text
복사
•
출력1
33
Plain Text
복사
더보기
제약 조건
•
•
문제 풀이
풀이1 브루트 포스 -
풀이2 그리디
풀이3 DP -
풀이 코드
•
Bottom-Up 방식의 구현
# Input
N = int(input())
arr = [0] + list(map(int, input().split()))
# Solve
dp = [0] * (N+1)
for i in range(1, N+1):
dp[i] = max(arr[i], dp[i-1]+arr[i])
print(max(dp[1:]))
Python
복사
Top-Down 방식의 구현