给定多时段股票价格，如何确定最优买入价以最大化收益？

这问题挺典型的，本质就是找「在某个时间点买入后，未来能卖到的最高价」的最大差值对吧？我来一步步拆解怎么做：

第一步：标准化时间格式 #

为了方便比较时间先后，先把所有12小时制的时间转换成24小时制的分钟数（比如09:00 a.m. = 960=540分钟，1:00 p.m. = 1360=780分钟）。这样所有时间都变成数字，更容易排序和比较。

以你的示例输入为例，转换后会得到这些区间：

• (540, 600, 80)
• (540, 660, 50)
• (600, 660, 30)
• (600, 780, 90)
• (660, 840, 70)
• (720, 840, 40)
• (840, 900, 60) # 假设你最后一个区间是到15:00，价格暂定为60

第二步：优化计算逻辑（避免暴力枚举） #

如果暴力枚举所有买入-卖出组合，当区间数量多的时候效率会很低。更好的方式是从后往前遍历，记录当前能遇到的最高卖出价，这样每个区间只需要计算一次利润：

1. 先把所有区间按「结束时间」从晚到早排序。
2. 初始化三个变量：max_sell_price（记录当前之后能卖到的最高价）、max_profit（记录当前最大利润）、best_buy_price（记录最优买入价）。
3. 遍历每个区间：
   • 计算当前区间买入的利润：current_profit = max_sell_price - current_price
   • 如果current_profit大于max_profit，就更新max_profit和best_buy_price为当前区间的价格。
   • 如果当前区间的价格大于max_sell_price，就更新max_sell_price（因为这个区间的时间更早，后面的买入操作可以用这个价格卖出）。

第三步：结合示例计算 #

按上面的逻辑遍历示例区间：

1. 第一个遍历的是(840,900,60)：max_sell_price初始为60，利润0，无更新。
2. 第二个是(720,840,40)：利润60-40=20，大于0，所以max_profit=20，best_buy_price=40；max_sell_price还是60。
3. 第三个是(660,840,70)：利润60-70=-10，小于20；但70>60，所以max_sell_price=70。
4. 第四个是(600,780,90)：利润70-90=-20，小于20；90>70，更新max_sell_price=90。
5. 第五个是(600,660,30)：利润90-30=60，大于20，所以max_profit=60，best_buy_price=30；max_sell_price保持90。
6. 第六个是(540,660,50)：利润90-50=40，小于60；无更新。
7. 第七个是(540,600,80)：利润90-80=10，小于60；无更新。

最终得到最优买入价是Rs.30，最大利润是60。

代码实现（Python） #

def convert_time_to_minutes(time_str):
    # 处理类似"09:00 a.m."或"12:00 noon"的时间字符串
    if "noon" in time_str:
        return 12 * 60
    time_part, period = time_str.split()
    hour, minute = map(int, time_part.split(':'))
    if period.lower() == 'p.m.' and hour != 12:
        hour += 12
    elif period.lower() == 'a.m.' and hour == 12:
        hour = 0
    return hour * 60 + minute

def find_best_buy_price(intervals):
    # 转换所有时间为分钟数
    processed = []
    for interval in intervals:
        parts = interval.split(' - ')
        start_str, end_str, price_str = parts[0], parts[1], parts[2]
        start = convert_time_to_minutes(start_str)
        end = convert_time_to_minutes(end_str)
        price = int(price_str.replace('Rs. ', ''))
        processed.append( (end, start, price) )
    
    # 按结束时间从晚到早排序
    processed.sort(reverse=True, key=lambda x: x[0])
    
    max_sell_price = 0
    max_profit = -float('inf')
    best_buy_price = None
    
    for end, start, price in processed:
        current_profit = max_sell_price - price
        if current_profit > max_profit:
            max_profit = current_profit
            best_buy_price = price
        # 更新最高卖出价，因为当前区间的时间更早，后面的买入可以用这个价格卖出
        if price > max_sell_price:
            max_sell_price = price
    
    return f"Rs. {best_buy_price}" if best_buy_price is not None and max_profit > 0 else "No profitable opportunity"

# 示例输入
sample_input = [
    "09:00 a.m. - 10:00 a.m. - Rs. 80",
    "09:00 a.m. - 11:00 a.m. - Rs. 50",
    "10:00 a.m. - 11:00 a.m. - Rs. 30",
    "10:00 a.m. - 13:00 p.m. - Rs. 90",
    "11:00 a.m. - 14:00 p.m. - Rs. 70",
    "12:00 noon - 14:00 p.m. - Rs. 40",
    "14:00 p.m. - 15:00 p.m. - Rs. 60"
]

print(find_best_buy_price(sample_input))
# 输出：Rs. 30

注意：如果所有可能的利润都是负数（即未来没有更高的价格），那最优选择是不买入，代码里会返回"No profitable opportunity"。

内容的提问来源于stack exchange，提问作者Abhishek Goyal