Kadane's 알고리즘 (MCSS Maximum Contiguous Subsequence Sum)

주어진 배열에서 연속된 부분 구간의 합 중 최댓값을 구하는 문제 MCSS(Maximum Contiguous Subsequence Sum)

arr = [1, 2, 3, 4]
max_sum = arr[0]         # 전체 중 최댓값 저장
current_sum = arr[0]     # 현재 구간의 누적합

for i in range(1, len(arr)):
    if current_sum + arr[i] > arr[i]:
        current_sum += arr[i]   # 누적합 유지
    else:
        current_sum = arr[i]    # 새 구간 시작

    if current_sum > max_sum:
        max_sum = current_sum   # 최댓값 갱신

print(max_sum)