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);
}

• Loki Astari: Don't pass the vector. Pass the iterator for begin and end. The size if then std::distance(begin, end)
• Loki Astari: If you know you are always in bounds use operator[] its not checked and thus faster that at()
• Ian Taylor: @lokiastari if i pass the iterator for begin and end, then how to i make the recursive calls?
• JS1: Question: did you purposefully not use the O(N) algorithm for finding the max sum subarray because you were required to use divide and conquer? Because the normal way to do it is only six lines long and faster.
• Ian Taylor: @JS1 yes, we were required to use the Divide & Conquer Approach. i do have an implementation of the approach you mentioned as well.

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));
}

• Ian Taylor: this definitely works, thanks -- the fact that i'm feeling shaky about the code means i should brush up on iterators and templates, but this is very much appreciated.
• Loki Astari: @IanTaylor: The only reason I used templates is because I was lazy and wanted to type I rather than std::vector<int>::iterator. The face that it works with other containers is just a bonus. If you don't like the templates you can remove them and just use std::vector<int>::iterator wherever I use I