largest sum in array

/* 19-7 You are given an array of integers (both positive and negative).

 Find the continuous sequence with the largest sum. Return the sum */

/* Unlike the linear algorithm solution provided in the book, my solution use divide and conquer, so as  to achieve O(log n) performance. */

#include <algorithm>

int getMiddleSum(int arr[], int len){

    int middle = len / 2; int sum = 0;

    int leftSum = 0; int head = 0;

    for (int i = 0; i < middle-1; i++) {

        leftSum += arr[i];

        if (leftSum < 0) {

            leftSum = 0;

            head = i + 1;

        }

    }

    int rightSum = 0; int tail = len - 1;

    for (int i = tail; i > middle; i--) {

        rightSum += arr[i];

        if (rightSum < 0) {

            rightSum = 0;

            tail = i - 1;

        }

    }

    for (int i = head; i <= tail; i++) {

        sum += arr[i];

    }

    return sum;

}

int largestSum(int arr[], int len){

    if (len == 1) {

        return arr[0];

    }

    if (len == 2) {

        if (min(arr[0], arr[1]) > 0) {

            return arr[0]+arr[1];

        } else {

            return max(arr[0], arr[1]);

        }

    }

    int middle = len / 2;

    int leftSum = largestSum(arr, middle);

    int rightSum = largestSum(&arr[middle], len-middle);

    int middleSum = getMiddleSum(arr, len);

    int maxSum = max(max(leftSum, rightSum), middleSum);

    return maxSum;

}