algorithm
최대 서브 어레이 알고리즘

최대 서브 어레이 알고리즘 기본 정보

최대 부분 배열 문제 는 가장 큰 합계를 갖는 1 차원 숫자 배열 내에서 인접한 부분 배열을 찾는 방법입니다.

이 문제는 원래 1977 년 Brown University의 Ulf Grenander 에 의해 디지털화 된 이미지에서 패턴의 최대 우도 추정을위한 단순화 된 모델로 제안되었습니다.

우리는 이와 같은 문제를 일으킬 수 있습니다. 다양한 정수 목록을 고려해 봅시다. 우리는 완전히 인접한 부분 집합이 가장 큰 합을 갖는 것에 관심을 가질 것입니다. 예를 들어 배열에 [0, 1, 2, -2, 3, 2] 가 있으면 최대 부분 배열은 [3, 2] 이고 합계는 5 입니다.

솔루션에 대한 브 루트 포스 접근법 :

이 방법은 솔루션을 찾는 데 가장 비효율적입니다. 이 과정에서 가능한 모든 하위 배열을 살펴본 다음 모든 배열의 합을 찾습니다. 마지막으로 모든 값을 비교하고 최대 하위 배열을 찾습니다.

Brute-Force 접근을위한 의사 코드 :

MaxSubarray(array)
  maximum = 0
  for i in input
    current = 0
    for j in input
       current += array[j]
       if current > maximum
         maximum = current
  return maximum

Brute-Force 방법의 시간 복잡도는 O(n^2) 입니다. 그럼 분단하고 정복하는 방법으로 움직여 봅시다.

해결 방법을 분단하고 정복하십시오.

왼쪽의 서브 어레이의 합, 오른쪽의 서브 어레이를 찾습니다. 그런 다음, 중앙 나누기를 가로 지르는 모든 것을 살펴보고 마지막으로 최대 합계를 반환하십시오. 이것이 나누기 및 정복 알고리즘이므로 두 가지 다른 기능이 필요합니다.

첫째, 분할 단계입니다.

maxSubarray(array)
  if start = end
    return array[start]
  else
    middle = (start + end) / 2
    return max(maxSubarray(array(From start to middle)), maxSubarray(array(From middle + 1 to end)), maxCrossover(array))

두 번째 파트에서는 ​​첫 번째 파트에서 생성 된 다른 파트를 분리합니다.

maxCrossover(array)
  currentLeftSum = 0
      leftSum = 0
  currentRightSum = 0
      rightSum = 0
  for i in array
    currentLeftSum += array[i]
    if currentLeftSum > leftSum
      leftSum = currentLeftSum
  for i in array
    currentRightSum += array[i]
    if currentRightSum > rightSum
      rightSum = currentRightSum
  return leftSum + rightSum

Divide and Conquer 방법의 시간 복잡도는 O(nlogn) 입니다. 그럼 동적 프로그래밍 접근법으로 넘어 갑시다.

동적 프로그래밍 접근법 :

이 솔루션은 Kadane의 알고리즘이라고도합니다. 선형 시간 알고리즘입니다. 이 해결책은 70 년대 후반 Joseph B. Kadane 이 제공합니다.

이 알고리즘은 루프를 통과하여 현재 최대 합계를 연속적으로 변경합니다. 흥미롭게도 이것은 동적 프로그래밍 알고리즘의 아주 간단한 예입니다. 중복 된 문제가 발생하고이를 줄여보다 효율적인 솔루션을 찾을 수 있기 때문입니다.

Kadane 's 알고리즘의 의사 코드 :

MaxSubArray(array)
  max = 0
  currentMax = 0
  for i in array
    currentMax += array[i]
    if currentMax < 0
      currentMax = 0
    if max < currentMax
      max = currentMax
  return max

Kadane 's Algorithm의 시간 복잡도는 O(n) 입니다.

C # 구현

public class MaximumSubarray
{
    private static int Max(int a, int b)
    {
        return a > b ? a : b;
    }

    static int MaxSubArray(int[] input, int n)
    {
        int max = input[0];
        int currentMax = input[0];
        for (int i = 1; i < n; i++)
        {
            currentMax = Max(input[i], currentMax + input[i]);
            max = Max(max, currentMax);
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return MaxSubArray(input, n);
    }
}