Maximum and minimum sum subsequences at a distance M

Given an array of numbers, find the maximum and minimum sum of sub sequences at a distance > M

E.g. arr = {3, 4, -2, 1, -2, 4, 6, -3, 5}, M = 2

max = 13 {4 + 4 + 5}, min = -5 {-2 -3}

This problem asks for the maximum and minimum sum generated by two subsequences (so non-contiguous values are allowed) whose values are distant at least \(M\) in the input array.

A dynamic programming approach can build upon the observation that the \(n^{th}\) value is either picked or discarded: if it is picked its value is added to the final result and the rest of the sum continues from the best value we had \(M\) positions away. If it is not, the best previous streak continues.

max_to_index(i) =
    if i is picked
      return value(i) + max_to_index(i - M)
    else
      return max_to_index(i - 1)

Here’s the \(O(N)\) algorithm in C++

template <typename T>
T subsequence_dist(std::vector<T>& vec, const unsigned int m,
                   T const&(*comp)(T const&, T const&) = std::max<T>) {
  std::vector<std::vector<T>> dp(vec.size() + 1, std::vector<T>(2));
  dp[0][1] = vec[0];
  for (size_t i = 1; i < vec.size(); ++i) {
    dp[i][0] = (i - 1 >= 0) ? comp(dp[i - 1][0], dp[i - 1][1]) : 0;
    dp[i][1] = vec[i] +
         ((i - m - 1 >=0) ? comp(dp[i - m - 1][0], dp[i - m - 1][1]) : 0);
  }
  return comp(dp[vec.size() - 1][0], dp[vec.size() - 1][1]);
}