This post shares a very simple solution, whose code is rewritten below, just 5 lines :-)
1 class Solution { 2 public: 3 int maxProfit(vector<int>& prices) { 4 int low = INT_MAX, profit = 0; 5 for (int price : prices) { 6 low = min(low, price); 7 profit = max(profit, price - low); 8 } 9 return profit; 10 } 11 };
To give an explanation, suppose we denote p[n] to be the maximum profit we can earn from days 0 to n. Then we have the following DP recursive formula:
p[n + 1] = max(p[n], prices[n + 1] - min_{i = 0, ..., n}prices[i]).
The above code simply computes this formula :-)
