查找整型数组的元素之和最大的子串

#include<iostream> #include<utility> #include<tuple> #include<vector> #include<string> using std::cout; using std::endl; using std::string; template <typename T> void FindMaxSubArray( const T _arr[], const int _size ); template <typename T> T CalcArraySum(const T _arr[], const std::pair<int, int> & _indexPair); template <typename T> void PrintArray(const T _arr[], const std::pair<int, int> & _indexPair); template<typename T> void PrintSectionVector(const std::vector<std::tuple<int, int, T> > &_vec, const string &_tip); template <typename T> T GetMaxSumOfSection(const std::vector<std::tuple<int, int, T> > &_vec); int main() { int data1[] {-3, -2, 4, 1, 2, 0, -8, 5, 4, 0, 2, -6, 7, 20, -5}; FindMaxSubArray<int>(data1, sizeof(data1) / sizeof(int)); int data2[] {1,-5,0,-9,-6,40,1,0, 8, 9, -200, 3, 4, 5, 7, 8, 31,-20, 0, 1, 0, -2}; FindMaxSubArray<int>(data2, sizeof(data2) / sizeof(int)); int data3[] {-3, -2, -8, -6, -5, -4, -100, -8, -4}; FindMaxSubArray<int>(data3, sizeof(data3) / sizeof(int)); return 0; } template <typename T> void FindMaxSubArray( const T _arr[], const int _size ) { int idx = -1, start = -1, end = -1; T max = 0; std::vector<std::tuple<int, int, T> > devidedVec, mergedVec, maxSumVec; PrintArray<T>(_arr, std::make_pair(0, _size - 1) ); for(idx=0; idx < _size; ){ start = idx; if( _arr[idx] >= 0 ){ for( ; idx < _size && _arr[idx] >= 0; ++idx ); } else{ for( ; idx < _size && _arr[idx] < 0; ++idx ); } end = idx - 1; devidedVec.push_back(std::tuple< int, int, T>(start, end, CalcArraySum( _arr, std::make_pair(start, end)))); } if(devidedVec.size() == 1 && std::get<2>(*(devidedVec.begin())) < 0){ idx = 0; max = _arr[0]; for(int i = 0; i < _size; ++i){ if( max < _arr[i]){ idx = i; max = _arr[i]; } } maxSumVec.push_back(std::tuple<int, int, T>(idx,idx, max)); PrintSectionVector(devidedVec, "devidedVec"); PrintSectionVector(mergedVec, "mergedVec"); PrintSectionVector(maxSumVec, "maxSumVec"); return; } T delta = 0; for(auto it1 = devidedVec.begin(); it1 != devidedVec.end(); ++it1){ if( std::get<2>(*it1) > 0 ){ mergedVec.push_back(*it1); delta = 0; for( auto it2 = it1 + 1; it2 != devidedVec.end(); ++it2 ){ delta += std::get<2>(*it2); if( delta >= 0 ){ mergedVec.push_back(std::tuple<int,int,T> (std::get<0>(*it1), std::get<1>(*it2), std::get<2>(*it1) + delta)); } } } } max = GetMaxSumOfSection<T>( mergedVec ); for(auto it = mergedVec.begin(); it != mergedVec.end(); ++it ){ if( max == std::get<2>(*it) ) maxSumVec.push_back(*it); } PrintSectionVector(devidedVec, "devidedVec"); PrintSectionVector(mergedVec, "mergedVec"); PrintSectionVector(maxSumVec, "maxSumVec"); return; } template<typename T> T CalcArraySum( const T _arr[], const std::pair<int, int> & _indexPair) { T sum = 0; for(int i = _indexPair.first; i <= _indexPair.second; ++i){ sum += _arr[i]; } return sum; } template<typename T> void PrintArray( const T _arr[], const std::pair<int, int> & _indexPair) { cout << "-----------------------------------------------------------------------------\n"; cout << "array: \n\t"; for(int i = _indexPair.first; i <= _indexPair.second; ++i){ cout << _arr[i] << ", "; } cout << endl; } template<typename T> void PrintSectionVector( const std::vector<std::tuple<int, int, T> > &_vec, const string &_tip) { cout << _tip << " : \n"; for(auto it = _vec.begin(); it != _vec.end(); ++it ){ cout << "\t"; cout << "(" << std::get<0>(*it) << "," << std::get<1>(*it) << ") = " << std::get<2>(*it) << endl; } } template<typename T> T GetMaxSumOfSection( const std::vector<std::tuple<int, int, T> > &_vec ) { T max = 0; for(auto it = _vec.begin(); it != _vec.end(); ++it ){ if( max < std::get<2>(*it) ) max = std::get<2>(*it); } return max; }