BAEKJOON #1912 연속합

이 문제의 저작권은 BAEKJOON에 있습니다.

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

문제는 위 링크에서 확인할 수 있습니다.

N = input()
arr = list(map(int, input().split()))
ans = -1001
for i in range(1, len(arr)):
    arr[i] = max(arr[i-1] + arr[i], arr[i])
print(max(arr)) 

풀이

for문을 2개 사용해서 모든 연속합중에 작은 값을 찾을수도 있지만 그러면 시간이 너무 많이 걸리게됩니다.
이 문제는 규칙을 파악해서 점화식을 세워야 하는 문제입니다.
arr[i] = max(arr[i-1] + arr[i], arr[i])
위 코드는 배열의 i-1번째 수와 i번째 수를 더해 다시 i에 넣어주는 코드입니다.
하지만 배열의 i-1번째 수와 i번째 수를 더한 값이 i의 값보다 작을 수 있기 때문에 비교해서 큰 값을 넣어줍니다.
(문제의 조건이 큰 값을 구하는 것이기 때문입니다. 연속합이 작은 수는 필요 없기 때문에 i번째 숫자부터 다시 연속합을 구한다고 생각하면 편합니다.)