# Java DP Solution. Time O(n), Space O(1)

• ``````    public int maxProfit(int[] prices) {
// use dp idea to solve this problem
// m[i] represent i-th 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;
}
``````

• This post is deleted!

• Can you explain how the concept dynamic programming is applied here? Thanks!

• @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 i-th 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 i-th day, then the profit will be prices[i] - min.
Then m[i] should be the max of two cases.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.