카데인 알고리즘으로 subarray 최대합 구하기(동적 프로그래밍)

Kadane’s Algorithm

카데인 알고리즘은 배열에서 연속되는 부분의 최대 합을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 동적 프로그래밍의 한 형태로, 배열을 순회하면서 부분 배열의 최대 합을 계산합니다.

핵심 아이디어

우선 가장 왼쪽에서 시작해 오른쪽으로 이동하는 과정을 기준으로 잡습니다.

• 사용되는 변수
  • 지금까지 가장 큰 배열합을 저장해 놓을 변수
  • 새롭게 시작한 부분부터 지금까지 배열의 합

• 예제

  [1, -4, 3, 5, -1] 배열에서 연속된 배열의 합 중 가장 큰 값을 구하라.

  max_score = 지금까지 가장 큰 배열합을 저장해 놓을 변수 max_continue = 새롭게 시작한 부분부터 지금까지 배열의 합

  1. 현재 위치 1
     • max_continue = 1 ([1])
     • max_score = 1
  2. 현재 위치 -4
     • max_continue = 0 ([1+(-4)] 음수이므로 0으로 초기화)
     • max_score = 1 (1 > 1+(-4)이므로)
  3. 현재 위치 3
     • max_continue = 3 ([3])
     • max_score = 3 (3 > 1이므로)
  4. 현재 위치 5
     • max_continue = 8 ([3+5])
     • max_score = 8 (8 > 3이므로)
  5. 현재 위치 -1
     • max_continue = 7 ([3+5+(-1)])
     • max_score = 8 (8 > 7이므로)

코드 구현

def solution(n, k, a):
    # 기본적으로 왼쪽에서 오른쪽으로 가는 것을 기준으로 잡고 생각
    max_continue = 0 # 이어지는 최고값
    max_score = 0 # 현재까지 최고값
    for i in a:
        # 해당 요소가 마이너스 요소라면 굳이 왼쪽에서 오른쪽으로 올 필요 없음
        if max_continue+i < 0:
            max_continue=0
        else: # 만약 플러스 요소라면 추가적으로
            max_continue += i
            max_score = max(max_score, max_continue)
    return max_score