有一个整数数组price={7,1,5,3,6,4},price【i】代表第i天的股票价格,在每一天,你可以购买或者是售出股票,但是在任何时候最多只能持有一股股票求出,你能获得的最大利润。比如你在第0天购买的股票价值为7第二天选择抛售则亏损了6
时间: 2024-05-10 18:19:17 浏览: 14
这是一道经典的股票买卖问题,可以通过贪心算法来解决。
首先定义两个变量,一个是最小价格min_price,另一个是最大利润max_profit。我们从第一天开始遍历股票价格,如果当天的价格小于min_price,则更新min_price为当天的价格。否则,计算当天的价格与min_price之间的差值,如果这个差值大于max_profit,则更新max_profit为这个差值。遍历完所有的价格后,max_profit即为最大利润。
代码如下:
```python
def maxProfit(prices):
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
else:
max_profit = max(max_profit, price - min_price)
return max_profit
```
例如,对于数组price={7,1,5,3,6,4},调用maxProfit(price)函数将得到最大利润为5。
相关问题
给你一个正整数数组 price ,其中 price[i] 表示第 i 类糖果的价格,另给你一个正整数 k 。 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。 返回礼盒的 最大 甜蜜度
这是一个经典的二分答案问题。首先可以想到甜蜜度的上限为 max(price)-min(price),因为任意两个数的差值不可能超过这个范围。
然后我们可以考虑二分答案,假设当前二分到的甜蜜度为 mid,那么我们需要判断能否用 k 个礼盒将所有糖果都包装起来,使得每个礼盒内任意两个糖果的价格差不超过 mid。
这个问题可以使用贪心算法来解决。我们首先将价格数组按照从小到大排序,然后从前往后遍历。对于当前遍历到的糖果,我们尝试将其放入前面已经放置好的礼盒中,如果能够放入一个礼盒中使得这个礼盒内任意两个糖果的价格差不超过 mid,那么就将其放入该礼盒中。否则,我们就新开一个礼盒,并将当前糖果放入其中。
如果最终使用的礼盒数量不超过 k,那么说明当前的 mid 是可行的,我们可以继续尝试使用更大的 mid。否则,说明当前的 mid 不可行,我们需要尝试使用更小的 mid。
时间复杂度为 O(nlogn * log(max(price)-min(price)))。
第一行一个整数T(T <= 50),表示测试数据的组数。 每组测试数据有四行组成,前三行每行有两个整数S和P,分别表示每种苹果的大小(1 <= S <= 100)和价格(1 <= P <= 10000) 第四行有一个整数V(1 <= V <= 100,000,000)表示小姑娘袋子的大小。 Output 每组测试数据输出组数和小姑娘能得到的最大的价值。 Sample Input 1 1 1 2 1 3 1 6 Sample Output Case 1: 6
好的,以下是我为你编写的用C++语言实现的代码,用于计算小姑娘在神秘院子购买苹果所能获得的最大利润。
```c++
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct Apple {
int size;
int price;
};
bool cmp(Apple a, Apple b) {
return a.price > b.price;
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
vector<Apple> apples;
int s1, p1, s2, p2, s3, p3, v;
cin >> s1 >> p1 >> s2 >> p2 >> s3 >> p3 >> v;
apples.push_back(Apple{ s1, p1 });
apples.push_back(Apple{ s2, p2 });
apples.push_back(Apple{ s3, p3 });
sort(apples.begin(), apples.end(), cmp);
int res = 0;
for (int i = 0; i < 3 && v > 0; i++) {
int cnt = min(v / apples[i].size, apples[i].size);
res += cnt * apples[i].price;
v -= cnt * apples[i].size;
}
cout << "Case " << t << ": " << res << endl;
}
return 0;
}
```
该程序首先读入测试数据的组数,然后对于每组测试数据,读入三种苹果的大小和价格以及小姑娘带来袋子的大小。然后对三种苹果按照价格从高到低排序,依次选择价格高的苹果,直到小姑娘的袋子装满或者所有苹果都被购买完为止。最后输出小姑娘能够获得的最大利润。
希望这段代码能帮到你。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.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)