# O(n) time+O(n)space

• ``````typedef vector<int> vi;
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()) return 0;
int n = (int)prices.size();
vi prof(n,0);
for(int r=0;r<2;++r){
for(int i=1,m=prof[0]-prices[0];i<n;++i){
m = max(m,prof[i]-prices[i]);
prof[i] = max(prof[i-1],prices[i]+m);
}
}
return prof[n-1];
}
};
``````

The `prof` vector is storing the profit. `prof[i]` the maximum profit a person can get up to the ith day with at most r+1 transactions. And iterate r from 0 to 2-1.

• what does m means

• @chjxiao Sorry for the late reply.
Since in the `(r-1)th` outer loop: `prof[i]` is the maximum profit a person can get up to the `ith` day with at most `(r)` transactions. Then for the `(r)th` loop: we want to update `prof[i]` s.t. it is becomes the maximum profit one can get up to the `ith` day with at most `(r+1)` transactions. So actually we are maximizing the following:

``````prof[i] = max(prof[i-1] , max_{j: 1->i} (price[i] - price[j] + prof[j]) )
``````

The first term in the `max` function is easy to deal with. For the second term `max_{j: 1->i} (price[i] - price[j] + prof[j])`, we are tracking the maximum value of `- price[j] + prof[j]` during the loop, which is the `m` in the code. Since `price[i]` is fixed.

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