[알고리즘/백준] 1912: 연속합(python)
쉬운 문제인데 40분이나 고민했다...
| 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
|---|---|---|---|---|---|---|---|---|---|
| 10 | 6 | 9 | 10 | 15 | 21 | -14 | -2 | 19 | 18 |
| -4 | -1 | 0 | 5 | 11 | -24 | -12 | 9 | 8 | |
| 3 | 4 | 9 | 15 | -20 | -8 | 13 | 12 | ||
| 1 | 6 | 12 | -23 | -11 | 10 | 9 | |||
| 5 | 11 | -24 | -12 | 9 | 8 | ||||
| 6 | -29 | -11 | 4 | 3 | |||||
| -35 | -23 | -2 | -3 | ||||||
| 12 | 33 | 32 | |||||||
| 21 | 20 | ||||||||
| -1 |
모르겠어서 다 써봤다...
-4를 예로 들면 10까지 가장 큰 합은 10이고, -4까지는 두가지 경우가 있다. 10 -4 / -4
즉 자기 자신과 전의 가장 큰 합중에 max값을 구하면 된다.
max(dp[i-1]+a[i], a[i])
N = int(input())
a = list(map(int, input().split()))
dp = [0] * N
dp[0] = a[0]
for i in range(1, N):
dp[i] = max(dp[i - 1] + a[i], a[i])
print(max(dp))Author And Source
이 문제에 관하여([알고리즘/백준] 1912: 연속합(python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@y7y1h13/알고리즘백준-1912-연속합python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
