[파이썬/python] 백준 1912번 : 연속합(🥈2)

n = int(input())
arr = list(map(int,input().split()))
dp = [0] * n
dp[0] = arr[0]
for i in range(1, n):
    dp[i] = max(arr[i], dp[i-1] + arr[i])
print(max(dp))

지금까지 풀었던 피보나치와 유사한 형태 문제 말고 다른 문제를 접하니까 어떻게 풀지 감이 안 잡혀서 검색을 해봤다..

일단 arr의 길이와 같은 배열을 하나 더 만든다. 이 배열의 제일 첫 번째 값과 arr의 첫 번째 값은 같게 한다.

일단 arr[i]까지 계속 누적해서 더해온 값이 arr[i]보다 작으면 안 된다. 그래서 max함수를 이용하여 arr[i]까지의 누적값과 arr[i] 을 비교했을 때 누적값이 더 크면 dp[i]를 누적값으로, arr[i]이 더 크다면 dp[i]를 arr[i]로 바꿔주어 다시 arr[i]부터 누적값을 구한다.

그다음 dp배열의 최댓값을 구하면 답이 나온다.