动态规划解法
题目
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例
- 输入: prices = [7,1,5,3,6,4]
- 输出: 7
- 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
思路分析
dp[i][0]表示第i+1天交易完之后手里没有股票的最大利润
dp[i][1]表示第i+1天交易完之后手里持有股票的最大利润
递推公式
①第i+1天交易完之后手里持有股票
a. 当天没进行交易，但是手上有股票（前一天的）
b. 当天买入了股票（说明前一天手里没有股票）
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
取两者最大值
②第i+1天交易完之后手里没有股票
a. 当天没进行交易，手上又没有股票
b. 当天把手里的股票买了
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
取两者最大值
边界条件 --- 第一天
如果买入：dp[0][1] = -prices[0];
如果没买：dp[0][0] = 0;
代码实现
#define MAX(a, b) ((a > b) ? a : b)int maxProfit(int* prices, int pricesSize){ int (*dp)[2] = (int(*)[2])malloc(sizeof(int) * pricesSize * 2); if ((prices == NULL) || (pricesSize < 2)) return 0; // 初始条件 dp[0][0] = 0; // 第一天没有买股票 dp[0][1] = -prices[0]; // 第一天买了股票 // 注意这里的初始条件day从1开始,即从第二天开始. for (int day = 1; day < pricesSize; day++) { dp[day][0] = MAX(dp[day - 1][0], dp[day - 1][1] + prices[day]); dp[day][1] = MAX(dp[day - 1][1], dp[day - 1][0] - prices[day]); } // 最后一天手里没有持有股票,就是最大利润 return dp[pricesSize - 1][0];}
贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
分析
从这个模拟的股票涨跌图，可以看出其实我们不关心每天的股票价格，只需知道每两点之间的差值。然后将所有的正值（代表相对前一天是涨的）累加即可。
代码实现
int maxProfit(int* prices, int pricesSize){ int profits = 0; if ((prices == NULL) || (pricesSize < 2)) return 0; for (int i = 0; i < pricesSize - 1; i++) { if (prices[i] < prices[i + 1]) { profits += prices[i + 1] - prices[i]; } } return profits;}
号主：一枚机械专业本科生，经历了转行，从外包逆袭到芯片原厂的Linux驱动开发工程师，深入操作系统的世界，贯彻终身学习、终身成长的理念。平时喜欢折腾，寒冬之下，抱团取暖，期待你来一起探讨技术、搞自媒体副业，程序员接单和投资理财。【对了，不定期送闲置开发板、书籍、键盘等等】。
如果你想了解我的转行经验，欢迎找我交流~gongzhong号【哆哆jarvis】
一起不断探索自我、走出迷茫、找到热爱，希望和你成为朋友，一起成长~
