Улучшение моей реализации формы «разделяй и властвуй» для задачи максимального подмассива

Question

Я реализовал подход к методу «разделяй и властвуй» для решения задачи максимального подмассива. Я создал структуру для возврата решений

#pragma once

#include <iostream>
#include <vector>

template<class T> 
struct value { 
private:
    typedef typename std::vector<T>::iterator iter;
public:
    iter max_left;
    iter max_right;
    T sum;
};

Класс, содержащий методы stati c.

template<class T>
class SubArray
{
private:
    typedef typename std::vector<T>::iterator iter;

public:
    static void print(iter, iter);

    // Maximum Sub-Array
    static value<T> maximum_crossing_subarray(std::vector<T> &, iter, iter, iter);
    static value<T> maximum_subarray(std::vector<T> &, iter, iter);
};

И две реализации функций.

template<class T>
value<T> SubArray<T>::maximum_crossing_subarray(std::vector<T> & vec, iter low, iter mid, iter high) {
    iter max_left;
    iter max_right;

    T left_sum = std::numeric_limits<T>:: min();
    T right_sum = std::numeric_limits<T>:: min();

    T sum = 0;

    for (auto it = mid + 1; it-- != low;) {
        sum = sum + *it;
        if(sum > left_sum) {
            left_sum = sum;
            max_left = it;
        }
    }

    sum = 0;

    for (auto it = mid + 1; it <= high; ++it) {
        sum = sum + *it;
        if(sum > right_sum) {
            right_sum = sum;
            max_right = it;
        }
    }

    return value<T> { max_left, max_right + 1, right_sum + left_sum };
}

template<class T>
value<T> SubArray<T>::maximum_subarray(std::vector<T> & vec, iter low, iter high) {
    if(high == low) {
        return value<T> { low, high, *low };
    } else {
        iter mid = low + std::floor(std::distance(low, high)/2);
        value<T> left = maximum_subarray(vec, low, mid);
        value<T> right = maximum_subarray(vec, mid + 1, high);
        value<T> cross = maximum_crossing_subarray(vec, low, mid, high);
        if(left.sum >= right.sum && left.sum >= cross.sum) {
            return left;
        } else if(right.sum >= left.sum && right.sum >= cross.sum) {
            return right;
        } else {
            return cross;
        }
    }
}

Проблема в том, что когда я вызываю функцию, я должен указать ниже. -1 в звонке на maximum_subarray держит меня ночью. Могу ли я сделать что-нибудь, чтобы удалить его?

#include "algorithms/SubArray.h"

int main() {
    std::vector<int> max_me = { -1, 100, -5, -1, 20, 4, -3, 2, -6, 8, -10 };
    value<int> sub_array = SubArray<int>::maximum_subarray(max_me, max_me.begin(), max_me.end() - 1);
    std::vector<int> make_sub_array(sub_array.max_left, sub_array.max_right);
    // make_sub_array = 100 -5 -1 20 4 -3 2 -6 8

    return 0;
}

Answer 1

Во многих рекурсивных алгоритмах вы захотите иметь оболочку, которая принимает любые аргументы, которые вы хотите предоставить пользователю, а затем преобразует их в то, что действительно необходимо рекурсивной функции.

Таким образом, вы можете создать оболочку, которая принимает begin() и end() как вам нужно, а затем применяет - 1 к концу перед вызовом рекурсивной функции.