Java Solution: O(n) time, O(1) space

[santei]

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int maxProfit(final List<Integer> A) {
        int n = A.size();
        
        if (n <= 0) return 0;
        
        int maxProfitSoFar = 0;
        
        int min_price = A.get(0);
        
        for (int i = 1; i < n; i++) {
            min_price = Math.min(min_price, A.get(i));
            maxProfitSoFar = Math.max(maxProfitSoFar, A.get(i) - min_price);
        }
        
        return maxProfitSoFar;
    }
}