[백준] 1912번 (python 파이썬)

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

1912번: 연속합

 

 

주어진 수열과 같은 크기를 같는 배열을 만들어서 주어진 수열의 각 인덱스로 연속합이 끝나는 값으로 할당한다.

 

예를 들어보자.

주어진 수열을 A, 우리가 만들 수열을 B라고 한다.

A = [ 10, -4, 3, 1 ] 이면

B[0] = 10

B[1] = -4과 10-4 중 큰 것

B[2] = 3과 -4+3과 10-4+3 중 큰 것

B[3] = 1과 3+1과 -4+3+1과 10-4+3+1 중 큰 것

B = [ 10, 6, 9, 10 ] 이다

 

만약 A[4]로 5가 나오면 B[4]는 어떻게 될까?

B[4] = 5와 1+5과 3+1+5과 -4+3+1+5과 10-4+3+1+5 중 큰 것

그런데 위의 식들을 보면 겹치는 식이 보인다.

잘 생각 해보자.

B[3]의 뜻은 A[3]으로 끝나는 연속 합 중 제일 큰 값이다.

B[4]는 A[4]로 끝나는 연속 합 중에 제일 큰 값이어야 한다.

이는 B[3] + A[4] ( 앞서 제일 큰 값에 현재 값을 더한 것 ) 이거나, A[4] 둘 중 하나만 가능하다.

즉, B[4] = max( B[3]+A[4], A[4] )가 된다.

 

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

result_arr = arr.copy()

for i in range(1, n):
  result_arr[i] = max(result_arr[i], result_arr[i]+result_arr[i-1])
print(max(result_arr))