[알고리즘/백준] 1912: 연속합(python)

쉬운 문제인데 40분이나 고민했다...

10-43156-351221-1
1069101521-14-21918
-4-10511-24-1298
34915-20-81312
1612-23-11109
511-24-1298
6-29-1143
-35-23-2-3
123332
2120
-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))

좋은 웹페이지 즐겨찾기