public int maxProfit(int[] prices) {
// use dp idea to solve this problem
// m[i] represent ith day the max profit
// induction rule: for m[i], there are cases. case 1: dont sell at this day: m[i  1]
// case 2: sell at this day: prices[i]  globalMin
// m[i] = max(m[i  1], array[i]  globalMin)
// base case: m[0] = 0
// maintain a global min to indicate the best buy price
// time complexity is O(n), only check m[i  1]
// space complexity is O(1)
// sanity check
if (prices == null  prices.length <= 1) {
return 0;
}
int last = 0;
int min = prices[0];
for (int i = 1; i < prices.length; i++) {
last = Math.max(last, prices[i]  min);
min = Math.min(min, prices[i]);
}
return last;
}
Java DP Solution. Time O(n), Space O(1)


@zhongkong.hu
Basically m[i] represents the max profit for first i days. So I can use the previous result, which is m[i  1] to solve m[i]. There are two cases.
Case1: if you don't sell the stock at ith day, then you can check what's the max profit in first i  1 day(m[i  1]).
Case2: if you want to sell the stock at ith day, then the profit will be prices[i]  min.
Then m[i] should be the max of two cases.