Kadane's Algorithms

Maximum Subarray

// Kadane’s Algorithm (actually DP)
// maxSoFar maxEndHere
public static int maxSubArray(int[] A) {
    int maxSoFar=A[0], maxEndingHere=A[0];
    for (int i=1;i<A.length;++i){
        maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
        maxSoFar=Math.max(maxSoFar, maxEndingHere);    
    }
    return maxSoFar;
}

Best Time to Buy and Sell Stock

class Solution {
    public int maxProfit(int[] prices) {
        int maxEndHere = 0, maxSoFar = 0;
        for(int i = 1; i < prices.length; i++) {
            maxEndHere = Math.max(0, maxEndHere += prices[i] - prices[i-1]);
            maxSoFar = Math.max(maxEndHere, maxSoFar);
        }

        return maxSoFar;
    }
}