[알고리즘 공부] 1. 배열 최대 연속 부분합 (Kadane's Algorithm)

 

 

 

 

 

안녕하세요 오늘부터 알고리즘에 대해 공부하는 시간을 가져 보겠습니다.

 

문제는 다음과 같습니다. 

 

 

주어진 정수 배열에서 연속된 부분 배열 중 가장 큰 합을 구하는 문제를 해결하세요.

 

def max_subarray_sum(nums):
    # 초기화
    # 최대 합계 변수 음의 무한대로 초기화
    max_sum = float('-inf')
    # 현재 합계 변수 0으로 초기화
    current_sum = 0

    # 목록에 대한 반복
    for num in nums:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)

    return max_sum
    
    # 테스트
    nums = [-2,1,-3,4,-1,2,1,-5,4]
    print(max_subarray_sum(nums))  # 출력: 6 ([4,-1,2,1])

 

num = -2:

current_sum = max(-2, 0 + (-2)) = -2

max_sum = max(-inf, -2) = -2

 

num = 1:

current_sum = max(1, -2 + 1) = 1

max_sum = max(-2, 1) = 1

 

num = -3:

current_sum = max(-3, 1 + (-3)) = -2

max_sum = max(1, -2) = 1

 

num = 4:

current_sum = max(4, -2 + 4) = 4

max_sum = max(1, 4) = 4

 

num = -1:

current_sum = max(-1, 4 + (-1)) = 3

max_sum = max(4, 3) = 4

 

num = 2:

current_sum = max(2, 3 + 2) = 5

max_sum = max(4, 5) = 5

 

num = 1:

current_sum = max(1, 5 + 1) = 6

max_sum = max(5, 6) = 6

 

num = -5:

current_sum = max(-5, 6 + (-5)) = 1

max_sum = max(6, 1) = 6

 

num = 4:

current_sum = max(4, 1 + 4) = 5

max_sum = max(6, 5) = 6

 

반복을 마친 후 는 하위 배열의 최대 합인 max_sum입니다 6[4, -1, 2, 1]

따라서 함수는 6을 반환합니다.

 

 

Kadane의 알고리즘은 다양한 분야 및 시나리오, 특히 인접한 하위 배열 또는 시퀀스의 최적화 및 분석과 관련된 분야 및 시나리오에 적용할 수 있는 다용도 기술입니다.

 

주식 시장 분석:

일일 주가 변동 목록이 주어지면 Kadane의 알고리즘은 주가가 가장 많이 상승하는 기간을 결정하여 최적의 매수 및 매도 시기를 나타낼 수 있습니다.

이미지 처리:

픽셀 값의 2D 배열로 표현된 이미지에서 Kadane의 알고리즘을 확장하여 이미지의 가장 밝은 영역에 해당할 수 있는 최대 합계를 갖는 하위 배열을 찾을 수 있습니다.

생물정보학:

유전자 발현 수준의 순서를 분석할 때 알고리즘은 가장 높은 활동을 보이는 게놈 부분을 식별할 수 있으며, 이는 특정 생물학적 과정을 이해하는 데 중요할 수 있습니다.

 

요약하면 Kadane의 알고리즘은 다양한 유형의 데이터에서 연속 하위 배열의 최대 합계를 찾는 문제를 해결하기 위한 강력한 도구로, 이를 다양한 도메인에 걸쳐 광범위하게 적용할 수 있습니다.