#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]))
		// if we write:
		// S[l][k] = max(profit[j][k-1]-prices[j]), (j in [0, l)), then its equation is
		// S[l][k] = max(profit[l-1][k-1]-prices[l-1], S[l-1][k]).
		// Rewrite line 18 equation as equation set:
		//     S[i][k] = max(profit[i-1][k-1]-prices[i-1], S[i-1][k])
		//     profit[i][k] = max(profit[i-1][k], prices[i] + S[i][k])
		//
		int numOfDays = prices.size();
		int totalTransTime = times;
		// only need to construct one row
		// at day 0, no matter how many trans its all 0 profit.
		int* profit_i = new int[totalTransTime+1]();
		int* S = new int[totalTransTime+1]();
		for (int i = 0; i < totalTransTime + 1; i++)
			S[i] = INT_MIN;
		for (int i = 1; i < numOfDays; i++) {
			for (int k = totalTransTime; k > 0; k--) {
				int cand = profit_i[k - 1] - prices[i - 1];
				if (cand > S[k]) {
					S[k] = cand;
				}
				else
					S[k] = S[k];
				
				int term1 = profit_i[k];
				int term2 = prices[i] + S[k];

				profit_i[k] = term1 > term2 ? term1 : term2;
			}
		}
		return profit_i[totalTransTime];
	}
};

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

	return 0;
}