Maximum Subarray

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ret = A[0], sum = 0;
        for (int i = 0; i < n; ++i) {
            sum = max(sum + A[i], A[i]);
            ret = max(ret, sum);
        }
        return ret;
    }
};

divide and conquer approach

int maxSubArray(int A[], int n) {
    return maxSub(A,0,n-1);
}
int maxSub(int A[], int left, int right){
    if(left>right)return INT_MIN;
    if(left==right)return A[left];
    int mid=left+((right-left)>>1);
    int leftMax=INT_MIN, rightMax=INT_MIN;
    for(int i=mid-1, currSum=0; i>=left; --i)
        currSum+=A[i], leftMax=max(leftMax, currSum);
    for(int i=mid+1, currSum=0; i<=right; ++i)
        currSum+=A[i], rightMax=max(rightMax, currSum);
    int midMax=A[mid]+max(leftMax,0)+max(rightMax,0);
    return max(max(maxSub(A,left,mid-1),maxSub(A,mid+1,right)),midMax);
}

public int maxSubArray(int[] A) {
    int maxnow = 0;
    int maxall = A[0];
    for (int i = 0; i < A.length; i++) {
        maxnow = Math.max(0, maxnow + A[i]);
        if (maxnow > 0)
            maxall = Math.max(maxall, maxnow);
        else
            maxall = Math.max(maxall, A[i]);
    }
    return maxall;
}

class Solution {
public:
int maxSubArray(int A[], int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (n == 0) return INT_MIN;
    if (n==1) return A[0];
    int max_so_far = A[0];
    int max_end_here = A[0];
    for (int i=1;i<n;i++)
    {
        if (max_end_here <0)
            max_end_here = A[i];
        else
            max_end_here += A[i];
        max_so_far = max(max_so_far, max_end_here);
    }
    return max_so_far;
}
};

    int max = 1 << 31;
    int sum_for_now = 0;
    for( int i=0;i<n;i++)
    {
        sum_for_now += A[i];
        if( sum_for_now > max)
            max = sum_for_now;
        if( sum_for_now < 0)
            sum_for_now = 0;
    }
    return max;

int maxSubArray(int A[], int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (n==0) return 0;
    int sum = 0;
    int max = -1 * INT_MAX;

    for (int i=0; i<n; i++) {

        sum += A[i];
        if (sum > max) max = sum;
        if (sum < 0) sum = 0;
    }
    return max;
}

int maxSubArray(int A[], int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int local_max = 0, max = INT_MIN;

    for (int i = 0; i < n; i++) {
        local_max += A[i];
        if (local_max > max) {
            max = local_max;
        }
        if (local_max < 0) {
            local_max = 0;
        }
    }

    return max;
}

public class Solution {
public int maxSubArray(int[] A) {
    // Start typing your Java solution below
    // DO NOT write main() function
    int max = A[0];
    int sum = A[0];
    for(int i = 1; i < A.length; i++){
        sum = Math.max(A[i],sum+A[i]);
        max = Math.max(max,sum);
    }
    return max;
}

}

public class Solution {
public int maxSubArray(int[] A) {
    // Start typing your Java solution below
    // DO NOT write main() function
    int Max = A[0];
    int subMax = A[0];

    for(int i=1; i < A.length; i++){
        subMax = Math.max(A[i], A[i]+subMax);
        Max = Math.max(subMax, Max);
    }

    return Max;

}
}

int maxSubArray(int A[], int n) {
    int maxSum=INT_MIN, currSum=0;
    for(int i=0;i<n;++i)
        maxSum=max(maxSum,currSum=max(currSum+A[i],A[i]));
    return maxSum;
}

every max substring ending at A[i] is the maximum of A[i] and (max substring ending at A[i-1]) + A[i]