Maximum sub-array sum

Question

My code finds the maximum subarray sum and the starting and ending index of that subarray.

int Max(int a,int b){return (a>b)?a:b;}
int Max(int a,int b,int c){return Max(Max(a,b),c);}
int MaxAcrossSubArray(int arr[],int l,int m,int r,int &Start,int &End) 
{
    Start=m;//initialize start index
    int sum=arr[m];
    int sum_l=arr[m];
    for(int i=m-1;i>=l;--i)//include mid(---------|)
    {
        sum+=arr[i];
        if(sum>sum_l)
        {
            Start=i;
            sum_l=sum;
        }

    }
    End=m+1;//initialize end index
    sum=arr[m+1];
    int sum_r=arr[m+1];
    for(int i=m+2;i<=r;++i)//include mid(|-----------------)
    {
        sum+=arr[i];
        if(sum>sum_r){
            End=i;
            sum_r=sum;
        }
    }
    return sum_l+sum_r;//(-----------|---------------------)

}
int MaxSubArray(int arr[],int l,int r,int &Start,int &End)
{
    if(l==r)
    {
        Start=l;
        End=r;
        return arr[l];
    }

    else
    {
       int mid=(l+r)/2;
        int sA=-1,eA=-1,sB=-1,eB=-1,sC=-1,eC=-1;
        int a=MaxSubArray(arr,l,mid,sA,eA);
        int b=MaxSubArray(arr,mid+1,r,sB,eB);
        int c=MaxAcrossSubArray(arr,l,mid,r,sC,eC);
        int Maximum=Max(a,b,c);

        if(Maximum==a)
        {
            Start=sA;
            End=eA;
            return a;
        }

        else if(Maximum==b)
            {
                Start=sB;
                End=eB;
                return b;
            }
        else
            {
                Start=sC;
                End=eC;
                return c;
            }
    }
    }

}
int main()
{
    int arr[9]={-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int Start=-1;
    int End=-1;


    cout<<MaxSubArray(arr,0,8,Start,End)<<"\n";
    cout<<Start<<"\n";
    cout<<End<<"\n";
    for(int i=Start;i<=End;++i)
    {

        cout<<arr[i]<<"\t";
    }
    cout<<"\n";
    return 0;
}

Is there any way to optimize this?

Answer 1

Welcome to Code Review!

Algorithm

Since you specifically asked how to optimize the code, I'll put this part first. You are using a divide-and-conquer algorithm. This algorithm is \$\operatorname{\Theta}(n \log n)\$. There's a better \$\Theta(n)\$ algorithm which works like this: go through the array, from index i = [0, n). Keep track of two variables:

• max_sum: maximum subarray sum so far.

• max_end_sum: maximum subarray sum ending at index i.

Initially, both can be considered to be "negative infinity". At each element, these variables can be updated in constant time with the following formulas:

new_max_sum     = max{max_sum, array[i], max_end_sum + array[i]}
new_max_end_sum = max{array[i], max_end_sum + array[i]}

Readability

Code is read more than written. Here are some tips to improve readability:

• Always put a space after a comma and around binary operators. Instead of

  int c=MaxAcrossSubArray(arr,l,mid,r,sC,eC);
  

  Use

  int c = MaxAcrossSubArray(arr, l, mid, r, sC, eC);
  

• Always put the opening and closing braces of a function body on separate lines. Instead of

  int Max(int a,int b){return (a>b)?a:b;}
  

  Use

  int Max(int a, int b)
  {
      return (a > b) ? a : b;
  }
  

• Put a space after control keywords like for or if. This helps visually distinguish them from functions and operators (sizeof, typeid, etc.).

• Be consistent with indentation. Bad example:

  if(Maximum==a)
  {
      Start=sA;
      End=eA;
      return a;
  }
  
  else if(Maximum==b)
      {
          Start=sB;
          End=eB;
          return b;
      }
  

The standard library facilities

The function Max is already available in the standard library as std::max. For example:

std::max(42, 420) == 420
std::max({42, 420, 4200}) == 4200

(You may noticed that you need to use braces if the number of arguments is not exactly two.)

The following loop:

for(int i=Start;i<=End;++i)
{

    cout<<arr[i]<<"\t";
}

can be replaced by a call to std::copy with std::ostream_iterator.

In C++, raw C arrays are not recommended. You are advised to use standard library containers like std::array instead. Indexes should be of type std::size_t or std::ptrdiff_t instead of int.

Here's how the code may look like in modern C++, with iterators and tuples: (just a rough idea, not particularly optimized)

template <
    typename ForwardIt,
    typename Value,
    typename BinaryOp = std::plus<>,
    typename Compare = std::less<>
    >
std::tuple<ForwardIt, ForwardIt, Value>
maximum_subarray(ForwardIt first, ForwardIt last, Value init,
                 BinaryOp combine = {}, Compare compare = {})
{
    auto max_sum = std::make_tuple(first, first, init);
    auto max_end_sum = std::make_tuple(first, init);

    for (; first != last; ++first) {
        auto& [it, value] = max_end_sum;
        value = combine(value, *first);
        if (compare(value, *first)) {
            it = first;
            value = *first;
        }
        if (compare(std::get<2>(max_sum), value)) {
            max_sum = {it, std::next(first), value};
        }
    }

    return max_sum;
}

template <typename ForwardIt>
auto maximum_subarray(ForwardIt first, ForwardIt last)
{
    using Value = typename std::iterator_traits<ForwardIt>::value_type;
    return maximum_subarray(first, last, Value());
}