int maxProfit(vector<int>& prices) {

int n = prices.size();

int empty[n+2], exist[n+2];

exist[0] = INT_MIN;

exist[1] = INT_MIN;

empty[0] = 0;

empty[1] = 0;

for (int i = 0; i < n; ++i) {

empty[i+2] = max(empty[i+1], exist[i+1] + prices[i]);

exist[i+2] = max(exist[i+1], empty[i] - prices[i]);

}

return empty[n+1];

}

int maxProfit2(vector<int>& prices) {

/**

int n = prices.size();

int empty = 0, exist = INT_MIN, pre_empty = 0;

int temp;

for (int i = 0; i < n; ++i) {

temp = empty;

empty = max(temp, exist + prices[i]);

exist = max(exist, pre_empty - prices[i]);

pre_empty = temp;

}

return empty;

}

{

Solution s;

vector<int> vec = {1,2,3,0,2};

printf("%d", s.maxProfit(vec));

return 0;