企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：股票买卖

【题目描述】

给定一支股票接下来n nn天的价格，设计一个算法计算出最大的利润。

每天你可以进行买入或者卖出，或者不进行任何操作，但是需要遵守以下条件：

• 你不能同时参与多笔交易（你必须在再次买入前卖出之前的股票）。
• 卖出股票后，你无法在第二天买入股票（即冷冻期为1 11天）。

【输入】

第一行一个整数n ( 1 ≤ n ≤ 10 5 ) n(1≤n≤10^5)n(1≤n≤105)，表示一共有n nn天。

第二行一共有n nn个整数a i ( 1 ≤ a i ≤ 10 9 ) a_i(1≤a_i≤10^9)ai​(1≤ai​≤109)，表示第i ii天的价格。

【输出】

输出一行，包含一个整数，表示最大的利润。

【输入样例】

5 2 3 4 1 3

【输出样例】

3

【核心思想】

1. 问题分析：给定n nn天的股票价格a i a_iai​，每天可以买入、卖出或不操作，但不能同时持有多只股票（再次买入前必须卖出），且卖出后有1 11天冷冻期（第二天不能买入）。求最大利润。这是一个状态机 DP问题，需要设计多个状态表示不同的持仓和冷冻情况。

2. 算法选择：

   • 状态机 DP（线性 DP）：定义多个状态表示不同的交易状态
   • 状态设计：
     • 状态0 00：手中没有股票，且不在冷冻期（可以买入）
     • 状态1 11：手中持有股票
     • 状态2 22：手中没有股票，但处于冷冻期（刚卖出，不能买入）

3. 关键步骤：

   • 初始化：d p [ 0 ] [ 0 ] = 0 dp[0][0] = 0dp[0][0]=0（第0 00天没有股票，利润为0 00），其他状态初始化为负无穷
   • 状态转移：
     • d p [ i ] [ 0 ] = max ⁡ ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 2 ] ) dp[i][0] = \max(dp[i-1][0], dp[i-1][2])dp[i][0]=max(dp[i−1][0],dp[i−1][2])：状态0 00可以从状态0 00不操作，或从状态2 22冷冻期结束转移
     • d p [ i ] [ 1 ] = max ⁡ ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] − a [ i ] ) dp[i][1] = \max(dp[i-1][1], dp[i-1][0] - a[i])dp[i][1]=max(dp[i−1][1],dp[i−1][0]−a[i])：状态1 11可以从状态1 11继续持有，或从状态0 00买入（花费a [ i ] a[i]a[i]）
     • d p [ i ] [ 2 ] = d p [ i − 1 ] [ 1 ] + a [ i ] dp[i][2] = dp[i-1][1] + a[i]dp[i][2]=dp[i−1][1]+a[i]：状态2 22只能从状态1 11卖出股票转移（获得a [ i ] a[i]a[i]）
   • 答案：max ⁡ ( d p [ n ] [ 0 ] , d p [ n ] [ 2 ] ) \max(dp[n][0], dp[n][2])max(dp[n][0],dp[n][2])，最后不能持有股票

4. 时间/空间复杂度：

   • 时间复杂度：O ( n ) O(n)O(n)，一次遍历完成状态转移
   • 空间复杂度：O ( n ) O(n)O(n)，DP 数组存储，可优化至O ( 1 ) O(1)O(1)

5. 状态机 DP 的核心思想：

   • 状态设计：根据题目约束设计合理的状态，本题用三个状态表示持仓和冷冻情况
   • 状态转移：明确每个状态可以从哪些状态转移而来，确保状态转移的完备性
   • 最优子结构：当前最优解由子问题的最优解组合而成
   • 空间优化：由于只依赖前一天的状态，可以用滚动数组优化至O ( 1 ) O(1)O(1)
   • 适用于有复杂约束的序列决策问题，如股票交易、任务调度等

【算法标签】

#线性DP-一维

【代码详解】

#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;#defineintlonglongconstintN=1e5+5;intn,a[N],dp[N][5];// dp[i][j]: 前i天，状态j的最大收益signedmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];// 第i天的股价}memset(dp,-0x3f,sizeof(dp));// 初始化为负无穷dp[0][0]=0;// 第0天，没有股票for(inti=1;i<=n;i++){// 状态0: 没有股票，不操作dp[i][0]=max(dp[i-1][0],dp[i-1][2]);// 状态1: 持有股票dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i]);// 状态2: 卖出股票后的冷冻期dp[i][2]=dp[i-1][1]+a[i];}cout<<max(dp[n][0],dp[n][2]);// 最后不能持有股票return0;}

【运行结果】

5 2 3 4 1 3 3