这是悦乐书的第173次更新，第175篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第32题（顺位题号是122）。假设有一个数组，其中第i个元素是第i天给定股票的价格。设计算法以找到最大利润。可以根据需要完成尽可能多的交易（即，多次买入并卖出一股股票）。
注意：不能同时进行多笔交易（即，您必须在再次购买之前卖出股票）。
例如：
输入：[7,1,5,3,6,4]
输出：7
说明：在第2天买入（价格= 1）并在第3天卖出（价格= 5），利润= 5-1 = 4。然后在第4天买入（价格= 3）并在第5天卖出（价格= 6），利润= 6-3 = 3。
输入：[1,2,3,4,5]
输出：4
说明：在第1天买入（价格= 1）并在第5天卖出（价格= 5），利润= 5-1 = 4。请注意，您不能在第1天购买，在第2天购买并在以后出售，就像您一样同时参与多个交易。您必须在再次购买之前出售。
输入：[7,6,4,3,1]
输出：0
说明：在这种情况下，不进行任何交易，即最大利润= 0。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 解题
特殊情况一：当传入的数组为null时，直接返回0。
特殊情况二：当传入的数组不为null，但是其内只有0个或者1个元素时，无法支持买入并卖出操作，直接返回0。
正常情况：比之昨天的只能做一次交易，今天这道题可以进行多次交易，来求得最大利润，只要符合低买高卖，利润肯定是会大于0的。如果新的一天的价格比前一天的价格，两者之差就是利润，任意两个相邻的价格只要符合这个规则，都可以算作利润，并且题目也没有说卖出的当天不能再买入，所以依次比较相邻两元素并求差即可。
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int maxProfit = 0;
for (int i = 0; i < prices.length - 1; ++i) {
if (prices[i] < prices[i + 1]) {
maxProfit += prices[i + 1] - prices[i];
}
}
return maxProfit;
}
03 小结
此题的解法只用了一层循环，因此时间复杂度是O(n)；此题只创建了一个变量，因此空间复杂度是O(1)。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论