[백준/1912][Python] 연속합

문제

https://www.acmicpc.net/problem/1912

1912번: 연속합

풀이

내 스스로 풀지 못했다.

DP문제인데, 식 세우는 게 아직도 .. 부족하다. 더 열심히 하자.

일단 이중 for문으로 모든 경우를 탐색하는 건 n이 최대 100,000이라서 불가능하다.

arr[i-1] + arr[i]가 현재 원소 arr[i] 보다 크다면 최댓값이 계속 갱신되는 것이고,  
arr[i-1] + arr[i]가 현재 원소 arr[i] 보다 작다면, arr[i-1]이 음수라는 것이고, 그러면 i부터 새롭게 연속합을 시작

0번째 인덱스부터 6번째(-35)까지 max(arr[i],arr[i]+arr[i-1])을 한 결과, arr[6]에는 -14이 저장된다.이후 arr[7]인 12와 arr[6]+arr[7]의 값인 -2를 비교한다. 이때 arr[7]이 더 커서 값이 새로 갱신된다. 12부터 새로 덧셈을 시작해 나가는 것이다.
그리고, 6번째 인덱스의 값이 음수인 것이 자명해진다.

최댓값을 출력하는 이유는, 무조건 맨 마지막 값이 최댓값이 아니라, 값을 갱신해나가는 중에 최댓값이 나올 수 있기 때문이다. 

 

어렵다,...ㅠ

코드

n= int(input())
arr= list(map(int,input().split()))

for i in range(1,n):
    arr[i] = max(arr[i],arr[i]+arr[i-1]) #지금까지 더한것 중 최댓값이랑 현재거 더한거vs현재거
    #앞에까지 다 더한거의 최댓값이 10이었다. 근데 -30이 현재값이면 -30,10-30을 비교. -20으로 갱신.
    #그 다음에 더 큰수가 나오면, 새로 계산 시작.
    #즉, 이전까지의 합이 i번째 수보다 작으면? 이전 기록들은 무의미하다. 값을 새로 갱신하고 더하기 시작.
print(max(arr))