[algorithm] Kadene`s Algorithm

Maximum subarray problem

컴퓨터 과학에서 최대 최소 즉 최적화 문제는 항상 시간 및 공간 복잡도가 반드시 고민된다.
brute force로는 뭐든지 풀 수 있지만 우리의 비용이 항상 고려된다는 이야기이다.
오늘은 배열에서 최대 부분 배열의 합을 구하는 알고리즘에 대해 공부해보고자 한다.

Maximum subarray problem를 정의하면 아래와 같다.

배열에서 연속된 부분 배열중에서 가장 큰 합을 구하는 문제이다.

수열로 표현하면 아래와 같다.

$\sum_{x=i}^j A_{[x]}$

구체적인 예시를 들어보자.
[−2, 1, −3, 4, −1, 2, 1, −5, 4] 같은 배열이 있다.

여기서 가장큰 배열의 합은 아래와 같다.
[4, −1, 2, 1] >> 6

Maximum subarray problem의 properties

1. 모든 원소가 음이 아닌 정수인 경우: 전체의 합이 정답임이 자명하다.
2. 모든 원소가 양이 아닌 정수인 경우: 가장 큰 수 1개가 정답이거나 공배열이 된다.
3. 몇몇 부분 배열이 최대 합을 갖는 경우: 해당 배열의 합이 정답이다.

해당 문제에 대한 해결 방법

1. brute force
2. divide conquer
3. dynamic programming
4. reduction to shortest paths

우리는 시간 복잡도를 최소화 하는 다이나믹 프로그래밍에 대해서만 다루려고 한다.

Kadene`s Algorithm

카데네의 알고리즘은 비어있는 부분배열을 허용한다.

알고리즘의 방식은 아래와 같이 진행된다.
1. 왼쪽에서 오른 쪽으로 쭉 스캔한다.
2. i번째 스탭부터 j번째 스텝 이전까지의 현재 부분합을 구한다.
3. j 번째 스텝까지의 최대 부분합을 현재 부분합과 비교하면서 갱신해 나간다.

해당 알고리즘을 백날 말로 해봐도 이해하기 쉽지 않다. 아래의 수식을 봐보자.

결국엔 점화식으로 표현되기 때문에 dp로 진행하는 것이 적절하다.

파이썬 코드로 위의 내용을 구현하면 아래와 같다.

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""
    best_sum = 0
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

using dp in Maximum subarray problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

해결 방법

공간복잡도를 고려하지 않은 경우

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # dp 문제
        # 시간 복잡도를 최대한 n 으로 진행해보자.
        # 3가지 케이스로 나눌 수 있음
        # 이전것이 낫다.
        # 새로 시작하는 것이 낫다.
        # 합친 것이 낫다.
        dp = [0 for _ in range(len(nums))]
        dp[0] = nums[0]
        if len(nums) >= 2:
            for i in range(1, len(nums)):
                dp[i] = max(nums[i], dp[i-1] + nums[i])
        return max(dp)

공간 복잡도를 최소화 하는 경우

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best_sum = current_sum = float('-inf')
        for x in nums:
            current_sum = max(x, current_sum + x)
            best_sum = max(best_sum, current_sum)
        return best_sum

출처 https://en.wikipedia.org/wiki/Maximum_subarray_problem#Generalizations