2
\$\begingroup\$

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.

Follow up:

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;
}
```
\$\endgroup\$
2
  • 1
    \$\begingroup\$ It would be nice to see a more complete description of the problem as well as a link to the actual problem description. \$\endgroup\$
    – user33306
    Jan 9, 2020 at 0:46
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 9, 2020 at 9:34

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 9, 2020 at 15:16
  • \$\begingroup\$ 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. \$\endgroup\$
    – butt
    Jan 9, 2020 at 19:13
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$ Jan 9, 2020 at 14:57
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 9, 2020 at 15:13

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.