最大子数组有关问题
最大子数组问题
1. 问题描述
对于数组(如下),求解其最大子数组.
2. 算法设计
采用递归的方法求解
A. 求解数组左半部分的最大子数组
B. 求解数组右半部分的最大子数组
C. 求解整个数组的最大子数组
D. 比较A,B,C求出的结果,选出一个最大值,即为最终结果.
3. 数据结构设计
A. 中间结果的三元组,(子数组下标,子数组上标,子数组和)
class Tuple { public: int low, high, sum; Tuple(int l = 0, int h = 0, int s = 0):low(l), high(h), sum(s) { } };
B. 数组元素
std::vector<int> m_array;
4. 算法实现
算法实现文件: calc_max_subarray.h
#include <iostream> #include <vector> #include <cassert> #include <fstream> using namespace std; namespace nsp_subarray { class Tuple { public: int low, high, sum; Tuple(int l = 0, int h = 0, int s = 0):low(l), high(h), sum(s) { } }; class SubArray { private: std::vector<int> m_array; public: SubArray() { m_array.clear(); } virtual ~SubArray(){} void init_data(string fileName) { ifstream in(fileName.c_str()); while(!in.eof()) { int e = 0; in >> e; m_array.push_back(e); } } inline int get_array_size() { return m_array.size(); } Tuple find_max_crossing_subarray(int low, int mid, int high) { int m_leftSum = INT_MIN; int m_rightSum = INT_MIN; int m_maxLeft = mid; int m_maxRight = mid + 1; int sum = 0; for (int i = mid; i >= low; i--) { sum += m_array[i]; if (sum > m_leftSum) { m_leftSum = sum; m_maxLeft = i; } } sum = 0; for (int i = mid + 1; i <= high; i++) { sum += m_array[i]; if (sum > m_rightSum) { m_rightSum = sum; m_maxRight = i; } } return Tuple(m_maxLeft, m_maxRight, m_leftSum + m_rightSum); } Tuple find_maximum_subarray(int low, int high) { if (low == high) { return Tuple(low, high, m_array[low]); } else if (low < high) { int mid = (low + high) / 2.0; Tuple tLeft = find_maximum_subarray(low, mid); Tuple tRight = find_maximum_subarray(mid + 1, high); Tuple tCross = find_max_crossing_subarray(low, mid, high); if (tLeft.sum >= tRight.sum && tLeft.sum >= tCross.sum) { return tLeft; } else if (tRight.sum >= tLeft.sum && tRight.sum >= tCross.sum) { return tRight; } else { return tCross; } } } }; };
5. 使用方法
主文件: main.cpp
#include<iostream> #include "calc_max_subarray.h" using namespace std; using namespace nsp_subarray; int main() { SubArray a; Tuple t; a.init_data("A.txt"); t = a.find_maximum_subarray(0, a.get_array_size() - 1); return 0; }
6. 文件内容
文件为: A.txt,内容如下.
13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7