https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
给出股票每一天的价格,求解只做一次交易的最佳收益方案。
思路是首先建立一个存储股票每天差价的数组 diff[],其中 diff[i] = prices[i] - prices[i - 1],这样原问题就变成了最大连续子数组和的问题。
int maxProfit(int* prices, int pricesSize) { if (!pricesSize) return 0; int * diff = (int*)malloc(pricesSize * sizeof(int)); diff[0] = 0; for (int i = 1; i < pricesSize; ++i) { diff[i] = prices[i] - prices[i - 1]; } int max_val = 0; int curr_val = 0; for (int curr = 0; curr < pricesSize; ++curr) { curr_val += diff[curr]; if (curr_val > max_val) { max_val = curr_val; } else if (curr_val < 0) { curr_val = 0; } } free(diff); return max_val; }
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
此题很简单,因为可以做无限次交易,所以只要某一天的股票价格比前一天的大就可以计入总收益。
int maxProfit(int * prices, int pricesSize) { int ret = 0; for (int i = 1; i < pricesSize; ++i) { if (prices[i] > prices[i - 1]) ret += prices[i] - prices[i - 1]; } return ret; }
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
此题要求最多做两次交易,我们设置一个变量 i,从 0 变到 pricesSize,分别用第一题的办法检测 0 ~ i 和 i ~ pricesSize 的最大收益,并求和,因为差分数组比较大,所以先压缩一下,把连续的加和减序列分别合并。
int calc_max_sum(int *arr, int begin, int end) { int max_val = 0; int curr_val = 0; for (int curr = begin; curr < end; ++curr) { curr_val += arr[curr]; if (curr_val > max_val) { max_val = curr_val; } else if (curr_val < 0) { curr_val = 0; } } return max_val; } int shrink(int * diff, int size, int * compressed) { memset(compressed, 0, size * sizeof(int)); int count = 0; int index = 0; while (diff[++index] <= 0) ; while (index < size) { char move_count = 0; while (index < size && diff[index] >= 0) { compressed[count] += diff[index++]; move_count = 1; } if (move_count) { ++count; move_count = 0; } while (index < size && diff[index] <= 0) { compressed[count] += diff[index++]; move_count = 1; } if (move_count) { ++count; move_count = 0; } } return count; } int maxProfit(int* prices, int pricesSize) { int * diff = (int*)malloc(pricesSize * sizeof(int)); int * compressed = (int*)malloc(pricesSize * sizeof(int)); for (int i = 1; i < pricesSize; ++i) { diff[i] = prices[i] - prices[i - 1]; } int max_size = shrink(diff, pricesSize, compressed); //以i为分界,求0~i-1和i~n-1的最佳之和 int max_val = 0; for (int i = 0; i < max_size; ++i) { int curr_val = calc_max_sum(compressed, 0, i) + calc_max_sum(compressed, i, max_size); if (curr_val > max_val) { max_val = curr_val; } } free(compressed); free(diff); return max_val; }
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
此题要求最多 k 次交易时的最优化方案,一直没有想明白,后来理解了网友提供的方法才写出。
/*reference
http://m.blog.csdn.net/blog/elton_xiao/44676957 https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1
*/
int max(int x, int y) { return (x > y) ? x : y; } int special(int * prices, int pricesSize) { int ret = 0; for (int i = 1; i < pricesSize; ++i) { if (prices[i] > prices[i - 1]) ret += prices[i] - prices[i - 1]; } return ret; } int maxProfit(int k, int* prices, int pricesSize) { if (k >= pricesSize) return special(prices, pricesSize); int * sell = (int*)calloc(k + 1, sizeof(int)); int * buy = (int*)malloc(k * sizeof(int)); for (int i = 0; i < k; ++i) { buy[i] = INT_MIN; } for (int day = 0; day < pricesSize; ++day) { for (int i = 0; i < k; ++i) { sell[i] = max(sell[i], buy[i] + prices[day]); buy[i] = max(buy[i], sell[i + 1] - prices[day]); } } int ret = sell[0]; free(buy); free(sell); return ret; }