16529: 股票

greedy, http://cs101.openjudge.cn/practice/16529

假设小明一开始有100块钱，给出每天的股票价格，小明可以在这些天内先后进行一次买操作和一次卖操作，或者什么也不干。问小明最后最多可以得到多少钱？

注意：1. 一定要先买后卖

股票最后一定要卖掉
数据量较大，如果简单枚举（买入价，卖出价）会超时

输入

第一行为天数N(1 <= N <= 100000) 接下来一行有N个数Pi，为每天的股票价格，0 < Pi

输出

最后小明可以得到最多的钱数（小数点后保留两位）。

样例输入

Sample Input1
5
0.1 0.8 20 0.5 0.01

Sample Output1
20000.00

Sample Input2
6
599 600 301 599 300 301

Sample Output2
199.00

样例输出

Sample Input3
5
5 4 3 2 1

Sample Output3
100.00

Sample Input4
5
5 4 3 21 1

Sample Output4
700.00

提示：N天内只能买进一次，卖出一次。并且可以买非整数股。

来源：cs10117 Final Exam

python

'''
遍历数组，不断更新最小买入价格，同时计算当前价格与最小买入价格收益比，
如果这个比值大于已记录的最大差值，就更新最大差值。
'''
def max_profit(prices):
    # 保证有至少两天，否则无法完成一次买卖
    if len(prices) < 2:
        return 0.0
    
    # 初始化最小价格为第一天价格，最大利润为0
    min_price = prices[0]
    max_profit = 0.0

    # 遍历价格数组
    for price in prices:
        # 更新最小价格
        min_price = min(min_price, price)

        # 当前价格与最低购买价格比较，当前可能获得的最大利润
        profit = price / min_price

        # 更新最大利润
        max_profit = max(max_profit, profit)


    return 100 * max_profit

# 样例输入
days = int(input().strip())
prices = list(map(float, input().split()))

# 计算最大利润并输出，保留两位小数
result = max_profit(prices)
print("{:.2f}".format(result))

python

n=int(input())
A=[float(x)for x in input().split()]
r=1
p=A[0]
q=A[0]
for i in range(n):#min和max是遍历算法，会超时
    if A[i]>p:
        p=A[i]
        if p/q>r:
            r=p/q
    if A[i]<q:
        p=A[i]
        q=A[i]
print("%.2f"%(r*100))

16529: 股票 ​

16529: 股票