بزرگ ترین زیر آرایه ( maximum sub array ) :

پیدا کردن بزرگ ترین زیرآرایه در یک آرایه یکی از بهترین سوال ها برای پی بردن به ارزش روش تقسیم و حل است.در این سوال شما یک آرایه  (مجموعه) دارید و می خواهید بزرگ ترین زیرآرایه را در آن پیدا کنید .

ابتدا بگذارید مفهوم زیر آرایه را بیان کنیم : زیر آرایه بخشی از آرایه است که  تمام اجزای آن پشت سر هم آمده اند.برای مثال آرایه زیر را در نظر بگیرید :

-۱۰ , ۲ , ۳ , -۲ , ۶ , -۴ , ۶ , ۸ , -۴ , ۴ , -۵۰ , -۹

تعدادی از زیر آرایه ها آرایه بالا این ها می شوند:

-۱۰ , ۲ , ۳

-۴ , ۴ , ۴ , -۵۰

-۹

۶ , ۸ ,  -۴ ,  ۴

الگوریتم شما چیست ؟ اولین الگوریتمی که به ذهن بیشتر افراد می رسد   پیدا کردن تمام زیر آرایه ها است این الگوریتم  هزینه اش از مرتبه n^2 است .ولی ما در این پست الگوریتمی را بر مبنای روش تقسیم و حل ( divide and conquer ) ارایه می دهیم که از مرتبه  n*log n  است.

الگوریتم پیدا کردن بزرگ ترین زیر آرایه با استفاده از روش تقسیم و حل (Divide and conquer) :

هر آرایه ای با هر تعداد عضوی دارای این سه مشخصه است یکی خانه آغاز آرایه  (Low) و یکی هم خانه ی آخر آرایه (High) و دیگر هم خانه ی وسط (Mid) آرایه که در عکس زیر آن ها را مشخص کرده ام :

همین طور که در شکل بالا می بینید هر زیر آرایه حتما در یکی از این سه مکان قرار می گیرد :

۱- زیر آرایه ای که کلا در قسمت چپ Mid است که با رنگ سبز مشخص شده است.

۲- زیر آرایه ای که کلا در سمت راست Mid است که با زنگ قهوه ای مشخص شده است.

۳ – زیر آرایه ای که از Mid می گذرد و بخشی از آن در سمت راست Mid قرار دارد و بخشی از آن در سمت چپ Mid قرار دارد که با رنگ آبی مشخص شده است.

پیدا کردن بزرگ ترین زیر آرایه ای که جز قسمت سوم است بسیار آسان است و می توان آن را با تابع ای با هزینه ی n به دست آورد.

از آنجایی که توابع ما سه مقدار : خانه آغاز زیر آرایه ، خانه پایان زیر آرایه و مجموع اعضای زیر آرایه  را باید بر گرداند من کلاس زیر را تعریف کرده ام:

class arrayInformation
{
public:
	int sum;//sum of sub array element
	int low;//sub array start location
	int high;//sub array end location
};

ابتدا کد این تابع را در ببینید تا آن را را تو ضیح دهیم :

//find max crossing subarray
arrayInformation find_max_crossing_subarray(int *arr, int n, int low, int mid, int high)
{
	arrayInformation myarry;
	int leftSum = -2000000000;
	int rightSum = -2000000000;
	int sum = 0;

	for (int i = mid; i >= low; i--)
	{
		sum += arr[i];
		if (sum > leftSum)
		{
			leftSum = sum;
			myarry.low = i;
		}
	}
	sum = 0;
	for (int i = mid+1; i <= high; i++)
	{
		sum += arr[i];
		if (sum > rightSum)
		{
			rightSum = sum;
			myarry.high = i;
		}
	}
	myarry.sum = rightSum + leftSum;
	
	return myarry;
}

کد بالا تابع find_max_crossing_subarray است که قرار است بزرگترین زیر آرایه ای را که از Mid می گذرد پیدا کند.

آرگومان ها :

int *arr : آرایه است که قرار است پردازش روی آن انجام شود و به صورت pointer به تابع فرستاده شده است.

int n: تعداد اعضای آرایه arr است.

int low: نقطه آغاز آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را که از مرکز آن می گذرد پیدا کنیم.

int mid : نقطه وسط آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را که از مرکز آن می گذرد پیدا کنیم.

int high:نقطه آخر آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را که از مرکز آن می گذرد پیدا کنیم.

حلقه ی for اول قسمت چپ زیر آرایه که از مرکز می گذرد را پیدا می کند و مجموع اعضای آن و نقطه ی شروع آن را پیدا می کند.

حلقه ی for دوم قسمت راست زیر آرایه که از مرکز می گذرد را پیدا می کند و مجموع اعضای آن و نقطه ی آخر آن را پیدا می کند.

و  بعد مشخص شدن انتها و ابتدای زیر آرایه مورد نظر و مجموع اجزایش آن را در یک شی از کلاس arrayInformation به نام myarray می ریزد و آن را به عنوان خروجی تابع بر می گرداند.

حالا نوبت تابع اصلی برنامه است که برزگ ترین زیر آرایه را بر می گرداند :

arrayInformation find_max_subarray(int *arr, int n, int low, int high)
{
	arrayInformation leftArray;
	arrayInformation rightArray;
	arrayInformation midArray;
	arrayInformation myarray;
	if (low == high)
	{
		myarray.sum = arr[high];
		myarray.low = low;
		myarray.high = high;
	}
	else
	{
		int mid = (low + high) / 2;
		leftArray = find_max_subarray( arr, n, low, mid);
		rightArray = find_max_subarray( arr, n, mid + 1, high);
		midArray = find_max_crossing_subarray( arr, n, low, mid, high);
		
		if (leftArray.sum > rightArray.sum)
		{
			if (leftArray.sum > midArray.sum)
			{
				myarray = leftArray;
			}
			else
			{
				myarray = midArray;
			}
		}
		else
		{
			if (rightArray.sum > midArray.sum)
			{
				myarray = rightArray;
			}
			else
			{
				myarray = midArray;
			}
		}
	}
	return myarray;
}

آرگومان ها تابع find_max_subarray :

int *arr : آرایه است که قرار است پردازش روی آن انجام شود و به صورت pointer به تابع فرستاده شده است.

int n: تعداد اعضای آرایه arr است.

int low: نقطه آغاز آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را  پیدا کنیم.

int high:نقطه آخر آرایه ای است که می خواهیم بزرگ ترین زیر دامنه ی آن را  پیدا کنیم.

در اول تابع شرطی وجود دارد که شرط پایان فراخوانی بازگشتی است که می گوید اگر Low برابر با High بود یا به عبارتی آرایه که در آن دنبال کوچک ترین زیر آرایه می گردیم کلا یک خانه داشت ، بزرگ ترین زیر آرایه آن خودش است.

اگر شرط برقرار نبود به else می رود  و در آن جا دو بار  خود find_max_subarray  فرا خوانی می شود و یک بار برای سمت چپ Mid یک بار برای سمت راست Mid و یک بار هم تابع find_max_crossing_subarray فراخوانی می شود. همین طور که می بینید مقدار بازگشت شده از سه فراخوانی بالا با هم مقایسه می شود و بزرگ ترین آن ها به عنوان مقدار خروجی find_max_subarray باز گردانده می شود .

در زیر کد برنامه پیدا کردن Maximum subarry را با زبان سی پلاس پلاس همراه با یک مثال فراخوانی می بینید :

// maximum sub array - divide and conquer.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream> 

using namespace std;

class arrayInformation
{
public:
	int sum;//sum of sub array element
	int low;//sub array start location
	int high;//sub array end location
};

//find max crossing subarray
arrayInformation find_max_crossing_subarray(int *arr, int n, int low, int mid, int high)
{
	arrayInformation myarry;
	int leftSum = -2000000000;
	int rightSum = -2000000000;
	int sum = 0;

	for (int i = mid; i >= low; i--)
	{
		sum += arr[i];
		if (sum > leftSum)
		{
			leftSum = sum;
			myarry.low = i;
		}
	}
	sum = 0;
	for (int i = mid+1; i <= high; i++)
	{
		sum += arr[i];
		if (sum > rightSum)
		{
			rightSum = sum;
			myarry.high = i;
		}
	}
	myarry.sum = rightSum + leftSum;
	
	return myarry;
}

arrayInformation find_max_subarray(int *arr, int n, int low, int high)
{
	arrayInformation leftArray;
	arrayInformation rightArray;
	arrayInformation midArray;
	arrayInformation myarray;
	if (low == high)
	{
		myarray.sum = arr[high];
		myarray.low = low;
		myarray.high = high;
	}
	else
	{
		int mid = (low + high) / 2;
		leftArray = find_max_subarray( arr, n, low, mid);
		rightArray = find_max_subarray( arr, n, mid + 1, high);
		midArray = find_max_crossing_subarray( arr, n, low, mid, high);
		
		if (leftArray.sum > rightArray.sum)
		{
			if (leftArray.sum > midArray.sum)
			{
				myarray = leftArray;
			}
			else
			{
				myarray = midArray;
			}
		}
		else
		{
			if (rightArray.sum > midArray.sum)
			{
				myarray = rightArray;
			}
			else
			{
				myarray = midArray;
			}
		}
	}
	return myarray;
}
//open-mind.ir
int main()
{
	arrayInformation maximumArray;
	int *arr = new int[9];

	arr[0] = 0;
	arr[1] = 5;
	arr[2] = 6;
	arr[3] = -100;
	arr[4] = 20;
	arr[5] = 15;
	arr[6] = -2;
	arr[7] = -50;
	arr[8] = 10;
	
	maximumArray = find_max_subarray(arr, 8, 0, 8);
	cout << "array start at: " << maximumArray.low << endl;
	cout << "array end at  : " << maximumArray.high << endl;
	cout << "array sum     : " << maximumArray.sum << endl;
	return 0;
}

اگر الگوریتم دیگری دارید یا این برنامه را با زبان دیگر نوشته اید کدتان را برای ما ارسال کنید.