4
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Don't pass the vector. Pass the iterator for begin and end. The size if then std::distance(begin, end) \$\endgroup\$ – Martin York Apr 28 '15 at 1:49
  • \$\begingroup\$ If you know you are always in bounds use operator[] its not checked and thus faster that at() \$\endgroup\$ – Martin York Apr 28 '15 at 1:50
  • \$\begingroup\$ @lokiastari if i pass the iterator for begin and end, then how to i make the recursive calls? \$\endgroup\$ – Ian Taylor Apr 28 '15 at 1:55
  • \$\begingroup\$ 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. \$\endgroup\$ – JS1 Apr 28 '15 at 2:20
  • \$\begingroup\$ @JS1 yes, we were required to use the Divide & Conquer Approach. i do have an implementation of the approach you mentioned as well. \$\endgroup\$ – Ian Taylor Apr 28 '15 at 2:22
1
\$\begingroup\$

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));
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Ian Taylor Apr 28 '15 at 2:25
  • \$\begingroup\$ @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 \$\endgroup\$ – Martin York Apr 28 '15 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.