1055. 股票买卖 II
II
2023-09-27 14:27:32 时间
Powered by:NEFU AB-IN
文章目录
1055. 股票买卖 II
-
题意
给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 -
思路
- 贪心
- 首先,买卖长度大于1的操作,都可以拆解为多个当天买次天卖的操作,因为中途过程都被抵消了,只留下了端点
- 所以我们只需要判断次天的利润是否大于当天的利润即可,如果大于那么就进行一次操作即可
- dp
最后答案为 d p [ n ] [ 0 ] dp[n][0] dp[n][0],即最后未买入的状态
- 贪心
-
代码
贪心
n = int(input()) a = list(map(int, input().split())) ans = 0 for i in range(1, n): if a[i] - a[i - 1] > 0: ans += (a[i] - a[i - 1]) print(ans)
dp
''' Author: NEFU AB-IN Date: 2022-03-30 10:47:10 FilePath: \ACM\Acwing\1055.1.py LastEditTime: 2022-03-30 11:19:52 ''' N = int(1e5 + 10) dp = [[0] * 2 for _ in range(N)] n = int(input()) a = list(map(int, input().split())) a = [0, *a] dp[0][1] = -int(1e9) for i in range(1, n + 1): dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + a[i]) dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - a[i]) print(dp[n][0])
相关文章
- Leetcode: Search a 2D Matrix II
- 《Java核心技术 卷II 高级特性(原书第9版)》
- 【Luogu1414】又是毕业季II(数论)
- 基于支持向量机和NSGA-II的非晶合金变压器结构优化算法MATLAB仿真
- LeetCode227之基本计算器 II(相关话题:栈)
- 【LeetCode】81. Search in Rotated Sorted Array II (2 solutions)
- pgpool-II 高可用搭建
- nyoj 103-A+B Problem II (python 大数相加)
- [LeetCode] 685. Redundant Connection II 冗余的连接之二
- [LeetCode] 350. Intersection of Two Arrays II 两个数组相交之二
- [CareerCup] 15.2 Renting Apartment II 租房之二
- [LeetCode] 227. Basic Calculator II 基本计算器之二
- [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二
- 126. Word Ladder II