public class MaxSubSum3
{
  public static Retval maxSubSum3(int a[], int start, int end)
  {
    Retval rvleft, rvright, rvmiddle = new Retval();
    Retval rv = new Retval();

    if(end - start <= 0)
      return rv;
    else
    {
      int mid = (start + end)/2;// 2 sub arrays,  left[0:mid]  right[mid+1:end]
      rvleft = maxSubSum3(a, start, mid);
      rvright =maxSubSum3(a, mid+1, end); 
      int suml = 0;
      for(int i = mid; i >= start; i--)
      {
        suml = suml + a[i];
        if(suml > rvmiddle.getSum())
        {
          rvmiddle.setSum(suml);
          rvmiddle.setStart(i);
        }
      }
      int sumr = 0;
      int maxr = 0;
      for(int i = mid+1; i <= end; i++)
      {
        sumr += a[i];
        if(sumr > maxr)
        {
          maxr = sumr;
          rvmiddle.setEnd(i);
        }
      }
      rvmiddle.setSum(rvmiddle.getSum() + maxr);
      if(rvmiddle.getSum() > rvleft.getSum() && rvmiddle.getSum() > rvright.getSum())
        rv = rvmiddle;
      else if(rvleft.getSum() > rvmiddle.getSum() && rvleft.getSum() > rvright.getSum())
        rv = rvleft;
      else
        rv = rvright;
      return rv;
    }
  }
}