129. 1912(연속합)

import sys
input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))

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

문제요약

모든 경우의 연속된 수를 더 했을 때 가장 큰 수가 무엇인가? 

설명

리스트의 크기는 상관 없다.

들어온 입력의 리스트 만큼 사용할 것이다.

다음과 같이 숫자(현재 인덱스) 값과 숫자(현재 인덱스) + 숫자(현재 인덱스 - 1) 의 값 중 더 큰 것을 비교하여 본래 리스트에 덮어 씌운다.

 

예를들어 num[4]번째 에서 3번째 인덱스 값은 0 , 1 , 2 를 합 했을 경우 가장 큰 수를 나타낸다.

num[4] 입장에서는 자기 자신의 값 혹은 num[3]의 값 중 더 큰 것을 index = 4 (num[4]) 에 저장하면서 다음 값으로 진행한다.

 

즉, 최종 결과에서 각 인덱스의 값은 자기 자신의 인덱스 까지 연속된 합의 수중에서 제일 큰 수를 나타내는 것이다.

 

그 결과 중 가장 큰 수를 뽑는다면 제시된 수 중의 연속된 합 중에서 가장 큰 수를 뽑는 것이다.