#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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBJTlRfTUlOIC0yMTQ3NDgzNjQ3IAoKY2xhc3MgU29sdXRpb24gewpwdWJsaWM6CmludCBtYXhQcm9maXQodmVjdG9yPGludD4gJnByaWNlcywgaW50IHRpbWVzID0gMikgewoJLy8gY29ybmVyIGNhc2VzCglpZiAocHJpY2VzLnNpemUoKSA8PSAxKSByZXR1cm4gMDsKCgkvLyBkZWZpbmUgcHJvZml0W2ldW2tdIGF0IGkgZGF5LCBhdCBtb3N0IGsgdHJhbnNhY3Rpb25zCgkvLyAKCS8vIHRoZSByZWN1cnNpdmUgZXF1YXRpb24gaXM6CgkvLyBwcm9maXRbaV1ba10gPSBtYXgocHJvZml0W2ktMV1ba10sIC0+bGFzdCB0cmFuc0B0b2RheQoJLy8JCQkJCSAgbWF4KHByaWNlc1tpXS1wcmljZXNbal0rcHJvZml0W2pdW2stMV0pIC0+bGFzdCB0cmFuc0BkYXkgaikKCS8vCQkJCQkgIGhlcmUgaiBpcyBhdCByYW5nZSBbMCwgaS0xXQoJLy8gY2FuIGFsc28gYmUgcmV3cml0dGVuIGFzIAoJLy8gcHJvZml0W2ldW2tdID0gbWF4KHByb2ZpdFtpLTFdW2tdLCAKCS8vICAgICAgICAgICAgICAgICAgICBwcmljZXNbaV0rbWF4KHByb2ZpdFtqXVtrLTFdLXByaWNlc1tqXSkpCglpbnQgbnVtT2ZEYXlzID0gcHJpY2VzLnNpemUoKTsKCWludCBudW1PZlRyYW5zID0gdGltZXM7CgoJaW50KiogcHJvZml0ID0gbmV3IGludCpbbnVtT2ZEYXlzXTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbnVtT2ZEYXlzOyBpKyspCgkJcHJvZml0W2ldID0gbmV3IGludFtudW1PZlRyYW5zKzFdKCk7CgoJZm9yIChpbnQgaSA9IDE7IGkgPCBudW1PZkRheXM7IGkrKykgewoJCWZvciAoaW50IGsgPSAxOyBrIDw9IG51bU9mVHJhbnM7IGsrKykgewoJCQkvLyBmaW5kIG1heChwcm9maXRbal1bay0xXSAtIHByaWNlc1tqXSkgZm9yIGogWzAsaSkKCQkJaW50IFMgPSBJTlRfTUlOOwoJCQlmb3IgKGludCBqID0gMDsgaiA8IGk7IGorKykgewoJCQkJaW50IHRlbXAgPSBwcm9maXRbal1bayAtIDFdIC0gcHJpY2VzW2pdOwoJCQkJaWYgKHRlbXA+UykgUyA9IHRlbXA7CgkJCX0KCQkJaW50IHRlcm0xID0gcHJvZml0W2kgLSAxXVtrXTsKCQkJaW50IHRlcm0yID0gcHJpY2VzW2ldICsgUzsKCQkJcHJvZml0W2ldW2tdID0gdGVybTEgPiB0ZXJtMiA/IHRlcm0xIDogdGVybTI7CgkJfQoJfQoJcmV0dXJuIHByb2ZpdFtudW1PZkRheXMgLSAxXVtudW1PZlRyYW5zXTsKfQp9OwoKaW50IG1haW4oKSB7Cgl2ZWN0b3I8aW50PiB2eyAzLCAzLCA1LCAwLCAwLCAzLCAxLCA0IH07CglpbnQgcmV0OwoJcmV0ID0gKG5ldyBTb2x1dGlvbiktPm1heFByb2ZpdCh2KTsKCWNvdXQgPDwgcmV0OwoJcmV0dXJuIDA7Cn0=