LeetCode Maximum Subarray

General solution.
public int maxSubArray(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       int runningSum = 0;
       int totalSum = A[0];
       for (int i = 0; i < A.length; i++) {
           runningSum += A[i];
           if (runningSum > 0) {
               totalSum = Math.max(runningSum, totalSum);
           } else {
               totalSum = Math.max(totalSum, A[i]);
               runningSum = 0;
           }
       }
       return totalSum;
    }

DP
Memory optimization
public int maxSubArray(int[] A) {
        int maxEndingHere = A[0], maxSoFar = A[0];
        for (int i=1; i<A.length; i++) {
            maxEndingHere = Math.max(maxEndingHere + A[i], A[i]);
            maxSoFar = Math.max(maxEndingHere, maxSoFar);
        }
        return maxSoFar;
    }


D&C
Implement the binary search everywhere.
public int maxSubArray(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       int maxSum = Integer.MIN_VALUE;
       return findMaxSub(A, 0, A.length - 1, maxSum);
    }
 
    //Recursive to find max sum
    //may appear on the left, right or crossing the mid point
    private int findMaxSub(int[] A, int left, int right, int maxSum) {
        if (left > right) return Integer.MIN_VALUE;
     
        //Get Max sub by recursive ways
        int mid = (left + right)/2;
        int leftMax = findMaxSub(A, left, mid-1, maxSum);
        int rightMax = findMaxSub(A, mid+1, right, maxSum);
        maxSum = Math.max(maxSum, Math.max(leftMax, rightMax));
     
        //GEt Max sum by crossing mid
        int lSum = 0;
        int midLeftMax = 0;
        for (int i = mid-1; i>=left; i--) {
            lSum = lSum + A[i];
            if (lSum > midLeftMax) midLeftMax = lSum;
        }
     
        int rSum = 0;
        int midRightMax = 0;
        for (int i = mid+1; i<=right; i++) {
            rSum = rSum + A[i];
            if (rSum > midRightMax) midRightMax = rSum;
        }
        maxSum = Math.max(maxSum, midLeftMax + midRightMax + A[mid]);
        return maxSum;
    }