We create array profit, where profit[i] - maximum possible profit for day i (we sell stock not later day i) and variable Max stored maximum value of profit for last days if we have stock (NOT sell last time). If we **don't** sell stock at day i, profit[i]= profit[i-1]. If we **sell** stock at day we profit[i]= Max+prices[i]. So, **profit[i]= maximum(profit[i-1],Max+prices[i])**; Obviously, **profit[0]= 0**. And we remember about updating Max.

```
class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.size()<2) return 0;
int n= prices.size();
int profit[n];
profit[0]= 0;
int Max=-2000000000;
for (int i=1; i<n; i++)
{
profit[i]= max(max(profit[i-1],Max+prices[i]),prices[i]-prices[0]);
if (profit[i-1]-prices[i]>Max) Max= profit[i-1]-prices[i];
}
return profit[n-1];
}
};
```

and solution without array. (Memory O(1))

```
class Solution
{
public: int maxProfit(vector<int> &prices)
{
if (prices.size()<2) return 0;
int n= prices.size();
int pr1,pr2;
pr1= 0;
int Max= INT_MIN;
for (int i=1; i<n; i++)
{
pr2= max(max(pr1,Max+prices[i]),prices[i]-prices[0]);
if (pr1-prices[i]>Max) Max= pr1-prices[i];
pr1= pr2;
}
return pr1;
}
};
```