fork(1) 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. 		// if we write:
  23. 		// S[l][k] = max(profit[j][k-1]-prices[j]), (j in [0, l)), then its equation is
  24. 		// S[l][k] = max(profit[l-1][k-1]-prices[l-1], S[l-1][k]).
  25. 		// Rewrite line 18 equation as equation set:
  26. 		//     S[i][k] = max(profit[i-1][k-1]-prices[i-1], S[i-1][k])
  27. 		//     profit[i][k] = max(profit[i-1][k], prices[i] + S[i][k])
  28. 		//
  29. 		int numOfDays = prices.size();
  30. 		int totalTransTime = times;
  31. 		// only need to construct one row
  32. 		// at day 0, no matter how many trans its all 0 profit.
  33. 		int* profit_i = new int[totalTransTime+1]();
  34. 		int* S = new int[totalTransTime+1]();
  35. 		for (int i = 0; i < totalTransTime + 1; i++)
  36. 			S[i] = INT_MIN;
  37. 		for (int i = 1; i < numOfDays; i++) {
  38. 			for (int k = totalTransTime; k > 0; k--) {
  39. 				int cand = profit_i[k - 1] - prices[i - 1];
  40. 				if (cand > S[k]) {
  41. 					S[k] = cand;
  42. 				}
  43. 				else
  44. 					S[k] = S[k];
  45.  
  46. 				int term1 = profit_i[k];
  47. 				int term2 = prices[i] + S[k];
  48.  
  49. 				profit_i[k] = term1 > term2 ? term1 : term2;
  50. 			}
  51. 		}
  52. 		return profit_i[totalTransTime];
  53. 	}
  54. };
  55.  
  56. int main() {
  57. 	vector<int> v{ 3, 3, 5, 0, 0, 3, 1, 4 };
  58. 	int ret;
  59. 	ret = (new Solution)->maxProfit(v);
  60. 	cout << ret;
  61.  
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin 
Standard input is empty
stdout 
6
https://ideone.com/c1aiE4
Buy and sell stock k times. (DP equation set) 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!