백준 22.02.28. 1912번 - 연속합

---

↓ 틀린 코드

n = int(input())

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

result = -1001

sum = 0
for i in range(n):
    for j in range(n-i):
        for k in range(j, j+i+1):
            sum += arr[k]
        if sum > result:
            result = sum
        sum = 0
print(result)

수열의 합들을 모두 비교하여 그 중 최댓값을 출력하는 방식입니다.

시간초과가 나왔습니다.

---

n = int(input())

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


sum = [arr[0]]
for i in range(len(arr)-1):
    sum.append(max(sum[i] + arr[i + 1], arr[i+1]))
    
print(max(sum))

• 문제의 요지는 "연속되는 수열의 합 중 최댓값"이라는 것입니다.
• 때문에 최댓값을 갱신하는 방식으로 답을 구할 수 있습니다.
• (여태까지의 최댓값 + 수열의 다음 수) 와 (수열의 다음 수) 를 비교하여 최댓값이 큰 것으로 갱신하며 진행하면 됩니다.
• 시작할 때의 비교할 기준이 필요하기 때문에 arr[0]을 sum의 초깃값으로 할당해주었습니다.