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.

  
  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&lt;int&gt; &amp;vec) {
  if (vec.size() == 1) {
    return vec.at(0);
  }
  int midIndex = vec.size() / 2;
  vector&lt;int&gt; leftArray(vec.begin(), vec.begin() + midIndex);
  vector&lt;int&gt; 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&lt;int&gt; &amp;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 &gt; leftSum) leftSum = sum;
  }
  sum = 0;
  for (auto itr = vec.begin() + midIndex + 1; itr != vec.end(); ++itr) {
    sum += *itr;
    if (sum &gt; rightSum) rightSum = sum;
  }
  if (leftSum == INT_MIN || rightSum == INT_MIN) {
    return (leftSum == INT_MIN) ? rightSum : leftSum;
  }
  return (leftSum + rightSum);
}

int FindMaximumNumber(const int &amp;a, const int &amp;b, const int &amp;c) {
  if (a &gt;= b &amp;&amp; a &gt;= c) return a;
  if (b &gt;= a &amp;&amp; b &gt;= c) return b;
  if (c &gt;= a &amp;&amp; c &gt;= b) return c;
}
```
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.