content: package question0053_maximum_subarray;
  
  /**
   * 分治算法。
   *
   * 时间复杂度和空间复杂度均是O(nlogn)，其中n是nums数组的长度。
   *
   * 执行用时：2ms，击败97.99%。消耗内存：37.7MB，击败88.98%。
   */
  public class Solution2 {
      public int maxSubArray(int[] nums) {
          return maxSubArray(nums, 0, nums.length - 1);
      }
  
      private int maxSubArray(int[] nums, int left, int right) {
          if (left == right) {
              return nums[left];
          }
          int mid = left + ((right - left) >> 1), leftResult = maxSubArray(nums, left, mid),
                  rightResult = maxSubArray(nums, mid + 1, right), leftSum = 0, midLeftResult = Integer.MIN_VALUE,
                  rightSum = 0, midRightResult = Integer.MIN_VALUE;
          for (int i = mid; i >= left; i--) {
              leftSum += nums[i];
              midLeftResult = Math.max(midLeftResult, leftSum);
          }
          for (int i = mid + 1; i <= right; i++) {
              rightSum += nums[i];
              midRightResult = Math.max(midRightResult, rightSum);
          }
          return Math.max(leftResult, Math.max(rightResult, midLeftResult + midRightResult));
      }
  }