合計最大の領域を検索[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))

💡 トラブルシューティング方法

答えを間違える理由

-

💡 新知