[알고리즘 가이드 노트] 최대 연속 서열과

각각 두 가지 방법으로 실현한다.

나누어 다스리는 귀속 해법

선형 수학 해법

1. 나누어 다스리는 귀속 해법

세 가지 상황으로 나뉘어

최대 하위 서열과 완전히 왼쪽 하위 그룹에 있다

최대 하위 서열과 완전히 오른쪽 하위 그룹에 있다

중간을 넘었다

키 코드

/*  ， ，  mid   */
int findMaxCrossingSubArray(int * A, int low, int mid, int high)
{
	int leftIndex = mid;
	int rightIndex = mid;
	int leftSum = 0;
	int rightSum = 0;
	int leftFinalSum = A[mid];
	int rightFinalSum = 0;


	for (int i = mid; i >= 0; i--)
	{
		leftSum += A[i];
		if (leftSum > leftFinalSum)
		{
			leftIndex = i;
			leftFinalSum = leftSum;
		}
	}

	for (int i = mid + 1; i < high; i++)
	{
		rightSum += A[i];
		if (rightSum > rightFinalSum)
		{
			rightIndex = i;
			rightFinalSum = rightSum;
		}
	}

	return leftFinalSum + rightFinalSum;
}

int findMaximumSubarray(int *A, int low, int high)
{
	if (low == high)
	{
		return A[low];
	}
	//   mid  
	int mid = (high + low) / 2;
	int left = findMaximumSubarray(A, low, mid);
	int right = findMaximumSubarray(A, mid + 1, high);
	int cross = findMaxCrossingSubArray(A, low, mid, high);
	
	return max(max(left, right), cross);
}

2. 수학적 사고방식

만약 앞에서 더하기를 마이너스로 한다면 나는 더하지 않겠다고 선택하고, 정수라면 나는 가입할 것이다. 최종적으로 매번 가입할 때마다 이전의 결과와 비교하여 큰 값을 가지고 돌아와야 한다!intfindMaximumSubarray2(int*A, intsize) 참조;

키 코드

int findMaximumSubarray2(int *A, int size)
{
	int sum = 0;
	int result = A[0];
	for (int i = 0; i < size; i++)
	{
		if (sum < 0)
		{
			sum = 0;
		}

		sum += A[i];
		result = result > sum ? result : sum;
	}
	return result;
}

3. 요약

방법2의 시간 복잡도가 비교적 낮고 방법2는 인위적으로 분석과 취사를 했고 알고리즘을 정진하여 문제를 간단하게 만들었다.배우고 생각하지 않으면 망한다. 컴퓨터의 기술을 배운 후에 수학의 사고까지 더하면 왕왕 적은 노력으로 큰 효과를 거둔다!

전체 테스트 인증 코드:

#include "pch.h"
#include 

#define max(a, b) a > b ? a : b

int findMaxCrossingSubArray(int * A, int low, int mid, int high);
int findMaximumSubarray(int *A, int low, int high);
int findMaximumSubarray2(int *A, int size);

int main()
{
	int a[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
	std::cout << findMaximumSubarray(a, 0, 15) << std::endl;
	std::cout << findMaximumSubarray2(a, sizeof(a) / sizeof(a[0])) << std::endl;
	return 0;
}

/*  ， ，  mid   */
int findMaxCrossingSubArray(int * A, int low, int mid, int high)
{
	int leftIndex = mid;
	int rightIndex = mid;
	int leftSum = 0;
	int rightSum = 0;
	int leftFinalSum = A[mid];
	int rightFinalSum = 0;


	for (int i = mid; i >= 0; i--)
	{
		leftSum += A[i];
		if (leftSum > leftFinalSum)
		{
			leftIndex = i;
			leftFinalSum = leftSum;
		}
	}

	for (int i = mid + 1; i < high; i++)
	{
		rightSum += A[i];
		if (rightSum > rightFinalSum)
		{
			rightIndex = i;
			rightFinalSum = rightSum;
		}
	}

	return leftFinalSum + rightFinalSum;
}

int findMaximumSubarray(int *A, int low, int high)
{
	if (low == high)
	{
		return A[low];
	}
	//   mid  
	int mid = (high + low) / 2;
	int left = findMaximumSubarray(A, low, mid);
	int right = findMaximumSubarray(A, mid + 1, high);
	int cross = findMaxCrossingSubArray(A, low, mid, high);
	
	return max(max(left, right), cross);
}

int findMaximumSubarray2(int *A, int size)
{
	int sum = 0;
	int result = A[0];
	for (int i = 0; i < size; i++)
	{
		if (sum < 0)
		{
			sum = 0;
		}

		sum += A[i];
		result = result > sum ? result : sum;
	}
	return result;
}