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
comments (?)
stdin 
Standard input is empty
stdout 
6
https://ideone.com/eQX7vB
Buy and sell stock k times. (Raw DP) Explaination: http://p...content-available-to-author-only...t.com/2014/10/best-time-to-buy-and-sell-stock.html
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!