描述 给出n+1个正整数,第一个数字代表后面其他数字的总个数,从第二个数字开始,后面每个数字分别代表第1至n天货物对应的价格p。 假设老板只能选择某一天买入货物,并在未来的另一天卖出货物。请采用贪心算法设计一段程序,帮助老板计算通过一次买卖货物,他所能获取的最大利润。 返回老板可以从这笔交易中获取的最大利润。如果无法获取利润,则返回0。 示例 1: 输入:6 8 3 1 5 6 4 输出:5 解释:总共有6天,在第3天(价格为1)的时候买入,在第5天(价格为6)的时候卖出,最大利润为6-1=5。 注意:最大利润不能是 8-1=7, 因为卖出价格需要大于买入价格;同时不能在买入前卖出。 示例 2: 输入:6 9 7 6 3 2 1 输出:0 解释:总共有6天,每天的进货价格都高于后面的价格,无法通过卖出获取利润, 所以最大利润为0。 提示: 1 <= n <= 100 1 <= p <= 100。使用c语言实现
时间: 2024-02-18 22:59:47 浏览: 23
以下是使用C语言实现的贪心算法代码,可以解决该问题:
```c
#include <stdio.h>
int main() {
int n; // 货物总数
scanf("%d", &n);
int prices[n]; // 存储每天的货物价格
for (int i = 0; i < n; i++) {
scanf("%d", &prices[i]);
}
int max_profit = 0; // 最大利润
int buy_price = prices[0]; // 第一天的价格作为买入价格
for (int i = 1; i < n; i++) {
if (prices[i] > buy_price) { // 如果当前价格高于买入价格
int profit = prices[i] - buy_price; // 计算当前利润
if (profit > max_profit) { // 如果当前利润更高
max_profit = profit; // 更新最大利润
}
} else { // 如果当前价格低于或等于买入价格
buy_price = prices[i]; // 更新买入价格
}
}
printf("%d\n", max_profit);
return 0;
}
```
该算法的思路是,从第二天开始遍历每天的货物价格,如果当前价格高于买入价格,则计算当前利润并更新最大利润,否则更新买入价格。最后输出最大利润即可。因为只需要遍历一遍数组,所以时间复杂度为O(n),空间复杂度为O(n)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)