Given an integer array nums, find the subarray with the largest sum, and return its sum.

• Input:
  • nums = [-2,1,-3,4,-1,2,1,-5,4]
• Output:
  • 6
• Explanation:
  • The subarray [4,-1,2,1] has the largest sum 6.

• Input:
  • nums = [1]
• Output:
  • 1
• Explanation:
  • The subarray [1] has the largest sum 1.

• Input:
  • nums = [5,4,-1,7,8]
• Output:
  • 23
• Explanation:
  • The subarray [5,4,-1,7,8] has the largest sum 23.

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

1. Initialize Variables:

   • Set currentMax to the first element of nums.
   • Set globalMax to the first element of nums.

2. Iterate Through the Array:

   • Start from the second element and iterate through the array.
   • Update currentMax to be the maximum of the current element or the sum of currentMax and the current element.
   • Update globalMax to be the maximum of currentMax and globalMax.

3. Return the Result:

   • After iterating through the array, globalMax will hold the maximum subarray sum.

class Solution {
    public int maxSubArray(int[] nums) {
        int currentMax = nums[0];
        int globalMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            globalMax = Math.max(currentMax, globalMax);
        }
        return globalMax;
    }
}

This solution uses the divide and conquer approach to solve the problem in O(n log n) time complexity:

1. Divide the Array:

   • Split the array into two halves.
   • Recursively find the maximum subarray sum in the left half and the right half.

2. Find the Cross Sum:

   • Calculate the maximum subarray sum that crosses the midpoint. This sum includes elements from both the left and right halves.

3. Combine Results:

   • The result for the current array is the maximum of:
     • The maximum subarray sum in the left half.
     • The maximum subarray sum in the right half.
     • The maximum cross sum.

4. Return the Result:

   • The maximum of the three values above is the answer for the current array segment.

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;

        if(n == 0) throw new IllegalArgumentException("Invalid array given");

        return maxSubArray(nums, 0, n - 1);
    }

    private int maxSubArray(int[] nums, int l, int r) {
        if (l == r) return nums[l];

        int mid = l + (r - l) / 2;

        int leftMax = maxSubArray(nums, l, mid);
        int rightMax = maxSubArray(nums, mid + 1, r);
        int crossMax = crossMax(nums, l, r, mid);

        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    private int crossMax(int[] nums, int l, int r, int mid) {
        int leftSum = Integer.MIN_VALUE;
        int rightSum = Integer.MIN_VALUE;
        int sum = 0;

        for (int i = mid; i >= l; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }

        sum = 0;

        for (int i = mid + 1; i <= r; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }
}