本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing1054. 股票买卖 - AcWing题库【题目描述】给定一个长度为N NN的数组数组中的第i ii个数字表示一个给定股票在第i ii天的价格。如果你最多只允许完成一笔交易即买入和卖出一支股票设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。【输入】第一行包含整数N NN表示数组长度。第二行包含N NN个不大于10 9 10^9109的正整数表示完整的数组。【输出】输出一个整数表示最大利润。【输入样例】6 7 1 5 3 6 4【输出样例】5【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;intn;// 天数inta[N],dp[3][N];// a: 股票价格数组dp: 动态规划数组intmain(){cinn;// 输入天数for(inti1;in;i)// 输入每天的股票价格cina[i];memset(dp,-0x3f,sizeof(dp));// 初始化dp数组为负无穷for(inti1;in;i)// 初始化状态0不持有股票未完成交易的收益为0dp[0][i]0;for(inti1;in;i)// 动态规划递推{// 状态1持有股票// 转移方式// 1. 之前就持有股票继续持有dp[1][i-1]// 2. 今天买入股票dp[0][i-1] - a[i]从空仓状态买入dp[1][i]max(dp[1][i-1],dp[0][i-1]-a[i]);// 状态2不持有股票已完成一次交易// 转移方式// 1. 之前就已经完成交易dp[2][i-1]// 2. 今天卖出股票dp[1][i-1] a[i]从持有状态卖出dp[2][i]max(dp[2][i-1],dp[1][i-1]a[i]);}// 最终结果取两种情况的最大值// 1. 完成一次交易后不持有股票dp[2][n]// 2. 从未进行交易dp[0][n]初始为0coutmax(dp[2][n],dp[0][n])endl;return0;}【运行结果】6 7 1 5 3 6 4 5
