Maximum Subarray Algorithm

This problem can be solved use several different algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to shortest paths. If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is allowed). The maximal subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for maximal likelihood estimate of shapes in digitized pictures. There is some evidence that no significantly faster algorithm exists; an algorithm that solves the two-dimensional maximal subarray problem in O(n3−ε) time, for any ε>0, would imply a similarly fast algorithm for the all-pairs shortest paths problem. Grenander derived an algorithm that solves the one-dimensional problem in O(n2) time, better the brute force working time of O(n3).
class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int maxsum = A[0];
        int tempsum = A[0];
        for (int i = 1; i < n; i++) {
            if (tempsum < 0) tempsum = 0;
            tempsum += A[i];
            maxsum = max(maxsum, tempsum);
        }
        return maxsum;
    }
};

// 
// solution 2 : divide and conquer
//
class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        return maxSubArray(A, 0, n - 1);
    }
    
    int maxSubArray(int A[], int left, int right) {
        if (left > right)
            return INT_MIN;
        
        int mid = (left + right) / 2;
        int lmax = maxSubArray(A, left, mid - 1);
        int rmax = maxSubArray(A, mid + 1, right);
        
        int sum = 0, mlmax = 0;
        for (int i = mid - 1; i >= left; i--) {
            sum += A[i];
            mlmax = max(mlmax, sum);
        }
        sum = 0;
        int mrmax = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += A[i];
            mrmax = max(mrmax, sum);
        }
        
        return max(mlmax + A[mid] + mrmax, max(lmax, rmax));
    }
};

LANGUAGE:

DARK MODE: