# Finding maximum subarry sum

Looking for feedback on a question I solved in C++. It is a leetcode problem and I used divide and conquer to solve the problem.

### 53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.


If you have figured out the $$\\mathcal{O}(n)\$$ solution, try coding another solution using the divide and conquer approach, which is more subtle.

I am looking for feedback in terms of logic and also the implementation. If I search for a C++ solution online, I only see problem solved using arrays and I have used vector to solve to the problem while utilizing iterators.

Any feedback would be great.

Thanks!


int FindMaximumSubarray(const vector<int> &vec) {
if (vec.size() == 1) {
return vec.at(0);
}
int midIndex = vec.size() / 2;
vector<int> leftArray(vec.begin(), vec.begin() + midIndex);
vector<int> rightArray(vec.begin() + midIndex, vec.end());
int maximumSumLeftSubarray = FindMaximumSubarray(leftArray);
int maximumSumRightSubarray = FindMaximumSubarray(rightArray);
int maximumSumCrossingSubarray = FindMaximumSubarrayCrossing(vec);
return FindMaximumNumber(maximumSumLeftSubarray,
maximumSumRightSubarray,
maximumSumCrossingSubarray);
}

int FindMaximumSubarrayCrossing(const vector<int> &vec) {
int midIndex = vec.size() / 2, leftSum = INT_MIN, rightSum = INT_MIN, sum = 0;
for (auto itr = vec.rbegin() + midIndex; itr != vec.rend(); ++itr) {
sum += *itr;
if (sum > leftSum) leftSum = sum;
}
sum = 0;
for (auto itr = vec.begin() + midIndex + 1; itr != vec.end(); ++itr) {
sum += *itr;
if (sum > rightSum) rightSum = sum;
}
if (leftSum == INT_MIN || rightSum == INT_MIN) {
return (leftSum == INT_MIN) ? rightSum : leftSum;
}
return (leftSum + rightSum);
}

int FindMaximumNumber(const int &a, const int &b, const int &c) {
if (a >= b && a >= c) return a;
if (b >= a && b >= c) return b;
if (c >= a && c >= b) return c;
}
$$$$

• It would be nice to see a more complete description of the problem as well as a link to the actual problem description.
– user33306
Jan 9 '20 at 0:46
• For future reviews, remember that it helps reviewers to have a self-contained review, rather than having to infer the missing #include <vector> and using std::vector; that you've not shown. An example main() is always helpful, too. Jan 9 '20 at 9:34

You're creating a bunch of unnecessary vector copies. Try passing iterators into FindMaximumSubarray instead of a vector.

You can find the max of an initializer list of numbers using std::max.

You don't need to pass ints as const refs.

Are you sure this is more performant than a linear solution? What is your reasoning? Can we see your linear version?

Your code looks like it might have potential overflow errors. Maybe that's not important.

• I understand that I am creating several unnecessary vector copies but if I pass iterators how can I calculate the midIndex? Or is there a workaround for that? I have added std::max with an initializer. Why should I not pass ints as const refs? I am practising divide and conquer methodology hence I did not implement a linear solution but the above solution. Jan 9 '20 at 15:16
• You can use std::distance or just the - operator since they're vector iterators to get a integral distance between iterators. Ints generally shouldn't be const ref parameters because there's no advantage to it. A reference type is possibly bigger than an int, and it may confuse the compiler.
– butt
Jan 9 '20 at 19:13

# Consider the edge cases

The first thing I tried to do was:

#include <iostream>
int main()
{
std::cout << FindMaximumSubarray({});
}


This resulted in a stack overflow, since we check for a unitary vector but not for an empty one.

Consider using a larger type for the accumulator, as the sum is liable to overflow if the inputs are large. Ideally, you'd want to use a type that can represent SIZE_MAX times the range of int.

# Make good use of <algorithm>

Instead of FindMaximumNumber(), we can simply use std::max():

  return std::max({FindMaximumSubarray({vec.begin(), vec.begin() + midIndex}),
FindMaximumSubarray({vec.begin() + midIndex, vec.end()}),
FindMaximumSubarrayCrossing(vec)});


We can use std::find_if() to find the first and last positive values, immediately trimming off parts of the input which will never contribute.

# Other observations

Internal functions ought to have internal (static) linkage.

Use the correct type for midIndex - it should be a std::size_t. Simply using auto would avoid that mistake.

FindMaximumSubarrayCrossing contains two code blocks that are almost identical - it may be worth refactoring to reduce duplication.

When we test sum > leftSum, that's exactly equivalent (in the absence of overflow) to *itr > 0. That observation may help in identifying a more efficient algorithm.

Using INT_MIN as a marker is risky, given that that's a valid input value.

We could just use std::find_if() to locate zero-crossings and std::accumulate() to total each positive and each negative run. Then see which runs combine usefully.

• Thanks for the advice. I have fixed moved from my custom function to std::max(). It also makes sense to change midIndex from int to size_t. I did not understand your point about sum > leftSum. What would you recommend using if not INT_MIN? Jan 9 '20 at 14:57
• The observation that we only update leftSum when we're looking at a positive value is just an observation (not a criticism). It may help in understanding what we're looking for. You might be able to use LONG_MIN as a marker if long is big enough for any sum, but I think it could be clearer to maintain a separate boolean flag. Or use a std::optional` - that's the kind of thing it's for, after all. Jan 9 '20 at 15:13