089 연속합 2

첫번쨰 코드

 

오른쪽부터 시작한 합과 왼쪽부터 시작한 합을 모두 고려해야 하는 문제이다.

나도 처음에 단순하게 점화식을 작성했는데, 책에서 명확하게 이렇게 세우면 안된다는 예시였다 ㅎㅎ;

 

하여 점화식 아이디어와 코드는 책을 참고하였다.

 

import sys
input = sys.stdin.readline

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

left = [0] * n
left[0] = a[0]
result = left[0]

for i in range(1, n):
    left = max(a[i], left[i-1] + a[i])
    result = max(result, left[i])

right = [0] * n
right[n-1] = a[n-1]

for i in range(n-2, -1, -1):
    right[i] = max(a[i], right[i-1] + a[i])

for i in range(1, n-1):
    temp = left[i-1] + right[i-1]
    result = max(result, temp)

print(result)

 

통과!

아직은 이해가 버거워도 괜찮아!!

다양한 아이디어로 풀도록!

다음에 다시 풀어보자!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/13398.%E2%80%85%EC%97%B0%EC%86%8D%ED%95%A9%E2%80%852

programmers/백준/Gold/13398. 연속합 2 at main · ornni/programmers