算法导论第四章-分治策略-Cpp代码实现

第四章由一个股票交易问题，引出求最大子数组的问题。其实最大子数组的解法有很多，用动态规划我认为是最简单的方法。

这里使用了分治法，递归的思路很清晰。

divide_conquer.h

#pragma once

/*************************************************
Author:董小歪
Date:2016-06-08
Description:算法导论第四章-分治策略-Cpp代码实现
**************************************************/

#ifndef DIVIDE_CONQUER_H
#define DIVIDE_CONQUER_H

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

template<typename T>
class Divide_Conquer
{
public:
	typedef pair<pair<int, int>, T> mypair;		//返回值的结构定义
	Divide_Conquer();							//构造函数
	Divide_Conquer(const vector<T>& _data);		//构造函数
	mypair find_maximum_subarray();				//返回最大子数组的区间以及和
	void pirnt_data();							//打印数组
private:
	mypair find_maximum_subarray(int l, int h);					//返回最大子数组的和help函数
	mypair find_max_crossing_subarray(int l, int m, int h);
	vector<T> data;
};

template<typename T>
Divide_Conquer<T>::Divide_Conquer()
{
	data = vector<T>();
}

template<typename T>
Divide_Conquer<T>::Divide_Conquer(const vector<T>& _data)
{
	data = _data;
}

template<typename T>
pair<pair<int, int>, T> Divide_Conquer<T>::find_maximum_subarray()
{
	return find_maximum_subarray(0, data.size() - 1);
}

template<typename T>
pair<pair<int, int>, T> Divide_Conquer<T>::find_maximum_subarray(int l, int h)
{
	if (l == h)
		return make_pair(pair<int, int>(l, h), data[l]);
	else
	{
		int m = l + (h - l) / 2;
		mypair left_sum = find_maximum_subarray(l, m);
		mypair right_sum = find_maximum_subarray(m + 1, h);
		mypair cross_sum = find_max_crossing_subarray(l, m, h);
		if (left_sum.second > right_sum.second)
			if (left_sum.second > cross_sum.second)
				return left_sum;
			else
				return cross_sum;
		else
			if (right_sum.second > cross_sum.second)
				return right_sum;
			else
				return cross_sum;
	}
}

template<typename T>
pair<pair<int, int>, T> Divide_Conquer<T>::find_max_crossing_subarray(int l, int m, int h)
{
	int max_left = m, max_right = m + 1;
	T left_sum = data[m], right_sum = data[m + 1], sum = 0;
	for (int i = m; i >= l; --i)
	{
		sum += data[i];
		if (sum > left_sum)
		{
			left_sum = sum;
			max_left = i;
		}
	}
	sum = 0;
	for (int i = m + 1; i <= h; ++i)
	{
		sum += data[i];
		if (sum > right_sum)
		{
			right_sum = sum;
			max_right = i;
		}
	}
	return make_pair(pair<int, int>(max_left, max_right), left_sum + right_sum);
}

template<typename T>
void Divide_Conquer<T>::pirnt_data()
{
	for (const auto &var : data)
		cout << var << " ";
	cout << endl;
}

#endif // !DIVIDE_CONQUER_H
           

测试：

main_entrance.cpp

#include "divide_conquer.h"

int main()
{
	vector<int> data = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
	Divide_Conquer<int> dc(data);
	cout << "原数组：";
	dc.pirnt_data();

	Divide_Conquer<int>::mypair result = dc.find_maximum_subarray();
	cout << endl << "最大子数组的和为：" << result.second << endl;
	cout << "区别是[" << result.first.first << "," << result.first.second << "]" << endl;
	
	system("pause");
}
           

测试结果：