For each subarray, calculate four attributes:

```
mx (largest sum of this subarray),
lmx(largest sum starting from the left most element),
rmx(largest sum ending with the right most element),
sum(the sum of the total subarray).
```

The recurrence is: T(n) = 2T(n / 2) + O(1). So the running time of this algorithm is O(n).

```
class Solution {
public:
void maxSubArray(vector<int>& nums, int l, int r, int& mx, int& lmx, int& rmx, int& sum) {
if (l == r) {
mx = lmx = rmx = sum = nums[l];
}
else {
int m = (l + r) / 2;
int mx1, lmx1, rmx1, sum1;
int mx2, lmx2, rmx2, sum2;
maxSubArray(nums, l, m, mx1, lmx1, rmx1, sum1);
maxSubArray(nums, m + 1, r, mx2, lmx2, rmx2, sum2);
mx = max(max(mx1, mx2), rmx1 + lmx2);
lmx = max(lmx1, sum1 + lmx2);
rmx = max(rmx2, sum2 + rmx1);
sum = sum1 + sum2;
}
}
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
int mx, lmx, rmx, sum;
maxSubArray(nums, 0, nums.size() - 1, mx, lmx, rmx, sum);
return mx;
}
};
```