max_sub_sequence.hxx
Go to the documentation of this file.
1 /*===========================================================================================================
2  *
3  * SHA - Simple Hybesis Algorithms
4  *
5  * Copyright (c) Michael Jeulin-Lagarrigue
6  *
7  * Licensed under the MIT License, you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * https://github.com/michael-jeulinl/Simple-Hybesis-Algorithms/blob/master/LICENSE
11  *
12  * Unless required by applicable law or agreed to in writing, software distributed under the License is
13  * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and limitations under the License.
15  *
16  * The above copyright notice and this permission notice shall be included in all copies or
17  * substantial portions of the Software.
18  *
19  *=========================================================================================================*/
20 #ifndef MODULE_SEARCH_MAX_SUB_SEQUENCE_HXX
21 #define MODULE_SEARCH_MAX_SUB_SEQUENCE_HXX
22 
23 // STD includes
24 #include <iterator>
25 #include <utility>
26 
27 namespace SHA_Search
28 {
52  template <typename IT,
53  typename Distance = std::minus<typename std::iterator_traits<IT>::value_type>,
54  typename Compare = std::greater<typename std::iterator_traits<IT>::value_type>>
55  std::pair<int, int> MaxSubSequence(const IT& begin, const IT& end)
56  {
57  if (std::distance(begin, end) < 2)
58  return std::pair<int, int>(-1, -1);
59 
60  int minValIdx = 0;
61  std::pair<int, int> indexes(minValIdx, minValIdx);
62  auto minSum = static_cast<typename std::iterator_traits<IT>::value_type>(0);
63  auto currSum = *begin;
64  auto maxSum = *begin;
65 
66  for (auto it = begin + 1; it != end; ++it)
67  {
68  currSum += *it;
69  auto currentIdx = static_cast<int>(std::distance(begin, it));
70 
71  // keep track of the minimum sum and its first value index
72  if (Compare()(minSum, currSum))
73  {
74  minValIdx = currentIdx;
75  minSum = currSum;
76  }
77 
78  // Keeps track of the maximal sub array and its end value index
79  auto curMax = Distance()(currSum, minSum);
80  if (Compare()(curMax, maxSum))
81  {
82  indexes.first = minValIdx + ((*(begin + minValIdx) < 0) ? 1 : 0);
83  indexes.second = currentIdx;
84  maxSum = Distance()(currSum, minSum);
85  }
86  }
87 
88  return indexes;
89  }
90 };
91 
92 #endif // MODULE_SEARCH_MAX_SUB_SEQUENCE_HXX
std::pair< int, int > MaxSubSequence(const IT &begin, const IT &end)