22548: 机智的股民老张

http://cs101.openjudge.cn/practice/22548/

股民老张通过某种渠道事先知道了一支股票在未来几天的价格。老张获得了一个数组 a，其中 a[i] 是给定股票在第 i 天的价格。

现在老张希望通过选择某一天购买该股票并选择未来的另一天出售该股票来最大化他的利润。

返回老张可以从这次交易中获得的最大利润。 如果价格一直下跌，老张无法获得任何利润，则返回 0。

输入

由空格分开的若干非负整数，数组 a 的长度不超过 100,000，各元素 a[i] 满足 0 <= a[i] <= 10000。

输出

一个数，可以从这次交易中获得的最大利润

样例输入

7 1 5 3 6 4

样例输出

5

提示

在第二天买入（价格为 1），在第五天买出（价格为 6），因此收益为 5。

相反，如果输入为 7 6 5 4 3 1，则老张怎么买都不可能获得利润，因此返回 0。

隐式动态规划（Implicit Dynamic Programming）不需要使用 dp[i]显式地储存每一种可能的解。

总结：如何选择？

场景/需求	显式动态规划	隐式动态规划
是否需要完整路径	是，显式存储所有状态，方便回溯或输出路径。	否，只关心最终解时，用变量优化。
状态间的依赖复杂性	多状态依赖（如二维、全局依赖）需要显式保存。	少状态依赖（如前一项、前两项）时可以隐式。
问题规模/空间限制	问题规模小，内存充足时可以显式存储状态。	状态空间较大、内存紧张时，优先隐式优化。
实现难度	代码更直观，但可能较为冗长。	代码更紧凑，但需要更精细的优化。

在实际应用中，显式动态规划适合需要路径输出和复杂状态依赖的情况，隐式动态规划更适合大规模问题且仅需结果时的优化场景。

*a, = map(int, input().split())
min_price = float('inf')
max_profit = 0

for price in a:
    min_price = min(min_price, price)  # 更新最小值
    max_profit = max(max_profit, price - min_price)  # 更新最大利润

print(max_profit)

# 杨李捷飞 24工学院
a = list(map(int,input().split()))
n = len(a)
l1 = [a[0]]
for i in range(1,n):
    l1.append(min(a[i],l1[-1]))
l2 = [a[n-1]]
for i in range(n-2,-1,-1):
    l2.append(max(a[i],l2[-1]))
l2 = l2[::-1]
result = 0
for i in range(n):
    result = max(result,l2[i]-l1[i])
print(result)

思路：dp维护最小值，每次算出最后一天卖出时候能得到的钱，和钱的最大值比较，时刻更新

# 张清州 24化学与分子工程学院
a = list(map(int,input().split()))
income = 0
stack = []
min_value = float("inf")
for i in range (len(a)):
    min_value = min(a[i],min_value)
    income = max(income,a[i]-min_value)
print(income)