Program Listing for File max_subarray_finder.hpp

↰ Return to documentation for file (rcppsw/algorithm/max_subarray_finder.hpp)

#pragma once

/*******************************************************************************
 * Includes
 ******************************************************************************/
#include <algorithm>
#include <boost/optional.hpp>
#include <tuple>

#include "rcsw/common/fpc.h"

#include "rcppsw/rcppsw.hpp"

/*******************************************************************************
 * Namespaces/Decls
 ******************************************************************************/
namespace rcppsw::algorithm {

/*******************************************************************************
 * Class Definitions
 ******************************************************************************/
template <typename T>
class max_subarray_finder {
 public:
  boost::optional<std::tuple<T, int, int>> operator()(const std::vector<T>& arr) const {
    RCSW_FPC_NV(boost::none, arr.size() > 0);

    T max_sum = arr[0];
    T current_sum = arr[0];
    int start_index = 0;
    int end_index = 0;
    std::tuple<T, int, int> res;

    /* Kadane's algorithm - O(n) */
    for (size_t i = 0; i < arr.size(); ++i) {
      current_sum += arr[i];
      if (current_sum > max_sum) {
        max_sum = current_sum;
        end_index = i;
      } else if (current_sum < 0) {
        start_index = i + 1;
        current_sum = 0;
      }
    } /* for(i..) */
    return boost::make_optional(std::make_tuple(max_sum, start_index, end_index));
  }
};

} /* namespace rcppsw::algorithm */