Maximum sum subarray efficiency -- divide and conquer w/ vectors

Question

I have successfully implemented a divide and conquer approach for find the maximum sum subarray (see code below). The code works fine and is correct, however I have an efficiency problem in that in order to recursively calculate sub-vectors, I need to do a copying operation which ordinarily wouldn't be there.

I'm using vectors because the larger program, to which this algorithm belongs, needs to read from a file and parse to the vectors. The lines vary in length, and as a result I've used vectors so that I can easily read a line, parse it to a vector, and then run it through a series of similar algorithms.

My question is: I'm trying to find a way that I can retain the use of the vectors but eliminate the copy operations so that my algorithm best reflects the \$O(nlogn)\$ runtime that the divide and conquer MSS algorithm should have.

I've tried modifying the function's header to include range values as parameters, but I can't figure out how to make that work with vectors.

int algorithm_3(vector<int> vect){ 

    int n = vect.size(); // size of array

    // BASE CASE
    if(n == 1){
        return vect.at(0);
    }

    // RECURSIVE CALLS
    int m = n / 2;

    // ** INEFFICIENT COPY OPERATIONS ** // 
    vector<int> left_sub(vect.begin(), vect.begin() + m);
    vector<int> right_sub(vect.begin() + m, vect.end());

    int left_MSS = algorithm_3(left_sub);
    int right_MSS = algorithm_3(right_sub);


    // DETERMINE THE LEFTSUM AND RIGHTSUM FOR CASE 3: THE SUFFIX + PREFIX

    int leftsum = INT_MIN, rightsum = INT_MIN, sum = 0;
    for(int i = m; i < n; i++){
        sum += vect.at(i);
        rightsum = max(rightsum, sum);
    }

    sum = 0;
    for(int i = (m - 1); i >= 0; i--){
        sum += vect.at(i);
        leftsum = max(leftsum, sum);
    }

    int ans = max(left_MSS, right_MSS);

   return max(ans, leftsum + rightsum);
}

Answer 1

Most algorithms use iterators as the interface between themselves and the container. It abstracts away the actual container type and in cases likes this removes the need for a copy.

Prefer operator[] over at() when you already know that your index into the container is valid (the at() validates the index before doing the operation (useful when using unvalidated input but otherwise expensive).

template<typename I>
int sumSpecial(I loop, I end)
{
    int sum     = 0;
    int maxsum  = INT_MIN
    for(;loop != end; ++loop)
    {
        sum += *loop;
        maxsum = max(maxsum, sum);
    }
    return maxsum;
}
template<typename I>
int algorithm_3(I begin, I end){ 

    auto n = std::distance(begin, end);

    // BASE CASE
    if(n == 1){
        return *begin;
    }

    // RECURSIVE CALLS
    int m = n / 2;
    I mid = begin;
    std::advance(mid, m);

    int left_MSS = algorithm_3(begin, mid);
    int right_MSS = algorithm_3(mid, end);


    // DETERMINE THE LEFTSUM AND RIGHTSUM FOR CASE 3: THE SUFFIX + PREFIX

    int leftsum  = sumSpecial(std::reverse_iterator<I>(mid), std::reverse_iterator<I>(begin));
    int rightsum = sumSpecial(mid, end);

    int ans = max(left_MSS, right_MSS);

   return max(ans, leftsum + rightsum);
}

// Usage
int main()
{
    std::vector<int>   data = getData();
    std::cout << algorithm_3(std::begin(data), std::end(data));
}