[Judge] 합계가 가장 큰 구간 찾기

🎯 알고리즘 과제 - 합계가 가장 큰 구간 찾기

---

🤔 나의 풀이

📌 문제

- 알고리즘 과제 > 합계가 가장 큰 구간 찾기

📌 날짜

2020.04.15

📌 시도 횟수

5회

💡 Code

def solution(nlist, left, right):
    if left > right:
        return float("-inf")
    mid = (left + right) // 2
 
    left_max = sum_num = 0
    for i in range(mid - 1, left - 1, -1):
        sum_num += nlist[i]
        left_max = max(left_max, sum_num)
 
    right_max = sum_num = 0
    for i in range(mid + 1, right + 1):
        sum_num += nlist[i]
        right_max = max(right_max, sum_num)
 
    left = solution(nlist, left, mid - 1)
    right = solution(nlist, mid + 1, right)
 
    return max(left_max + nlist[mid] + right_max, max(left, right))
 
# 입력 및 실행 
for _ in range(int(input())):
    num = int(input())
    nlist = list(map(int, input().split()))
    print(solution(nlist, 0, len(nlist) - 1))

💡 문제 해결 방법

• left, right 중에 가장 큰 값 & left_max + mid + right_max : 둘 중 더 큰 값을 리턴(다시 left, right로) 하면서 최대로 이어진 연속된 숫자를 구한다.
• 

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

💡 새롭게 알게 된 점

---