Maximum Subarray

divide_and_conquer.cpp

#include <limits>

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n == 1)
            return A[0];
            
        auto mid = n / 2;
        
        auto r1 = (mid > 0) ? maxSubArray(A, mid) : numeric_limits<int>::min();
        auto r2 = ((n - (mid+1)) > 0) ? maxSubArray(A + (mid + 1), n - (mid+1)) : numeric_limits<int>::min();
        
        auto r3 = numeric_limits<int>::min();
        auto cur = A[mid];
        int left = 0, leftSum = 0;
        int right = 0, rightSum = 0;
        
        for (int i = 0; i < mid; ++i) {
            if (mid-1-i >= 0) {
                leftSum += A[mid-1-i];
                left = max(left, leftSum);
            }
            
            if (mid+1+i < n) {
                rightSum += A[mid+1+i];
                right = max(right, rightSum);
            }

            auto v1 = max(cur, cur + left);
            auto v2 = max(cur, cur + right);
            auto v3 = max(cur, cur + left + right);

            r3 = max(v1, v2);
            r3 = max(r3, v3);
        }
        
        // max(r1, r2, r3)
        auto res = max(r1, r2);
        return max(res, r3);
    }
};

dp.cpp

class Solution {
public:
    int maxSubArray(int A[], int n) {
        auto b = A[0];
        auto res = b;
        
        // 1) b[i] is the sum of the max sub array including element A[i], so b[i] = max(b[i-1] + A[i], A[i])
        // 2) the max sub array is the maximum of b[i] for i in [0, n)
        // 3) since only the latest b[i] is needed, use a single variable 'b' to represent that
        for (int i = 1; i < n; ++i) {
            b = max(A[i], b + A[i]);
            if (res < b)
                res = b;
        }
        
        return res;
    }
};