#include <iostream>
#include <vector>
using namespace std;

#define INT_MIN -2147483647 

class Solution {
public:
int maxProfit(vector<int> &prices, int times = 2) {
	// corner cases
	if (prices.size() <= 1) return 0;

	// define profit[i][k] at i day, at most k transactions
	// 
	// the recursive equation is:
	// profit[i][k] = max(profit[i-1][k], ->last trans@today
	//					  max(prices[i]-prices[j]+profit[j][k-1]) ->last trans@day j)
	//					  here j is at range [0, i-1]
	// can also be rewritten as 
	// profit[i][k] = max(profit[i-1][k], 
	//                    prices[i]+max(profit[j][k-1]-prices[j]))
	int numOfDays = prices.size();
	int numOfTrans = times;

	int** profit = new int*[numOfDays];
	for (int i = 0; i < numOfDays; i++)
		profit[i] = new int[numOfTrans+1]();

	for (int i = 1; i < numOfDays; i++) {
		for (int k = 1; k <= numOfTrans; k++) {
			// find max(profit[j][k-1] - prices[j]) for j [0,i)
			int S = INT_MIN;
			for (int j = 0; j < i; j++) {
				int temp = profit[j][k - 1] - prices[j];
				if (temp>S) S = temp;
			}
			int term1 = profit[i - 1][k];
			int term2 = prices[i] + S;
			profit[i][k] = term1 > term2 ? term1 : term2;
		}
	}
	return profit[numOfDays - 1][numOfTrans];
}
};

int main() {
	vector<int> v{ 3, 3, 5, 0, 0, 3, 1, 4 };
	int ret;
	ret = (new Solution)->maxProfit(v);
	cout << ret;
	return 0;
}