LeetCode

2015.4.17 05:27

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

　　The "Best Time to Buy and Sell Stock" series has been appearing in several version. Apparently this one is about dynamic programming.

　　At first I was a bit confused about the definition of "transaction" in the problem desription.

　　It was one "buy" or one "sell" that is defined as a "transaction", not one buy and one sell.

　　Thus here comes the typical two-demensional DP. Please see the code below, notice that the key idea lies in the local optimal and global optimal.

　　I haven't understood the algorithm well enough, though. Yet to think about it.

　　One thing is for sure: when k is greater than n, this problem is simplified to a greedy version.

Accepted code:

 1 // Yet to grasp the mechanism here... DP wasn't easy.
 2 #include <algorithm>
 3 #include <vector>
 4 using namespace std;
 5 
 6 class Solution {
 7 public:
 8     int maxProfit(int k, vector<int> &prices) {
 9         int n = prices.size();
10         
11         if (k >= n) {
12             return easyMaxProfit(prices);
13         }
14         
15         int i, j;
16         vector<int> local, global;
17         
18         local.resize(n + 1, 0);
19         global.resize(n + 1, 0);
20         int diff;
21         for (i = 1; i < n; ++i) {
22             diff = prices[i] - prices[i - 1];
23             for (j = k; j >= 1; --j) {
24                 local[j] = max(global[j - 1] + max(diff, 0), local[j] + diff);
25                 global[j] = max(global[j], local[j]);
26             }
27         }
28         return global[k];
29     }
30 private:
31     int easyMaxProfit(vector<int> &prices) {
32         int res;
33         int i, len = prices.size();
34         
35         res = 0;
36         for(i = 0; i < len - 1; ++i){
37             if(prices[i] < prices[i + 1]){
38                 res += prices[i + 1] - prices[i];
39             }
40         }
41         
42         return res;
43     }
44 };