find a subarray that contains the largest sum < k

find_subarray_closest_to_k.cpp

/* Given an array of integers A and an integer k, find a subarray that contains the largest sum, subject to a constraint that the sum is less than k?
*/
pair<int, int> FindSubarrayClosestToK(const vector<int>& a, int k) {
  pair<int, int> range{0, -1};

  if (a.empty()) return range;

  map<int, int> sum_to_idx;
  int sum = 0;
  int min_diff = k;
  sum_to_idx.emplace(0, -1);
  for (int i = 0; i < a.size(); ++i) {
    sum += a[i];
    auto it = sum_to_idx.upper_bound(sum - k); // -> use sum[i] - k < sum[j]
    if (it != sum_to_idx.end() && k - sum < min_diff) {
      range = {it->second + 1, i};
      min_diff = k - sum;
    }
    sum_to_idx.emplace(sum, i);
  }
  return range;
}