fork download
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. #define INT_MIN -2147483647
  6.  
  7. class Solution {
  8. public:
  9. int maxProfit(vector<int> &prices, int times = 2) {
  10. // corner cases
  11. if (prices.size() <= 1) return 0;
  12.  
  13. // define profit[i][k] at i day, at most k transactions
  14. //
  15. // the recursive equation is:
  16. // profit[i][k] = max(profit[i-1][k], ->last trans@today
  17. // max(prices[i]-prices[j]+profit[j][k-1]) ->last trans@day j)
  18. // here j is at range [0, i-1]
  19. // can also be rewritten as
  20. // profit[i][k] = max(profit[i-1][k],
  21. // prices[i]+max(profit[j][k-1]-prices[j]))
  22. int numOfDays = prices.size();
  23. int numOfTrans = times;
  24.  
  25. int** profit = new int*[numOfDays];
  26. for (int i = 0; i < numOfDays; i++)
  27. profit[i] = new int[numOfTrans+1]();
  28.  
  29. for (int i = 1; i < numOfDays; i++) {
  30. for (int k = 1; k <= numOfTrans; k++) {
  31. // find max(profit[j][k-1] - prices[j]) for j [0,i)
  32. int S = INT_MIN;
  33. for (int j = 0; j < i; j++) {
  34. int temp = profit[j][k - 1] - prices[j];
  35. if (temp>S) S = temp;
  36. }
  37. int term1 = profit[i - 1][k];
  38. int term2 = prices[i] + S;
  39. profit[i][k] = term1 > term2 ? term1 : term2;
  40. }
  41. }
  42. return profit[numOfDays - 1][numOfTrans];
  43. }
  44. };
  45.  
  46. int main() {
  47. vector<int> v{ 3, 3, 5, 0, 0, 3, 1, 4 };
  48. int ret;
  49. ret = (new Solution)->maxProfit(v);
  50. cout << ret;
  51. return 0;
  52. }
Success #stdin #stdout 0s 3476KB
stdin
Standard input is empty
stdout
6