【题目来源】https://www.acwing.com/problem/content/1057/【题目描述】给定一个长度为 N 的数组数组中的第 i 个数字表示一个给定股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。【输入格式】第一行包含整数 N表示数组长度。第二行包含 N 个不大于 10000 的正整数表示完整的数组。【输出格式】输出一个整数表示最大利润。【输入样例1】67 1 5 3 6 4【输出样例1】7【输入样例2】51 2 3 4 5【输出样例2】4【输入样例3】57 6 4 3 1【输出样例3】0【样例解释】样例1在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3 。共得利润 43 7。样例2在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。样例3在这种情况下, 不进行任何交易, 所以最大利润为 0。【数据范围】1≤N≤10^5​​​​​​​【算法分析】● 状态定义dp[i][0]第 i 天结束时不持有股票的最大收益dp[i][1]第 i 天结束时持有股票的最大收益● 转移分析最后一步分析法1. dp[i][0]第 i 天不持有股票。两种来源- 前一天本来就不持有今天什么都不做dp[i-1][0]- 前一天持有股票今天卖出dp[i-1][1] a[i]dp[i][0]max(dp[i-1][0],dp[i-1][1]a[i])2. dp[i][1]第 i 天持有股票。两种来源- 前一天已经持有今天不动dp[i-1][1]- 前一天无股票今天买入dp[i-1][0]-a[i]dp[i][1]max(dp[i-1][1],dp[i-1][0]-a[i])● 边界dp[0][0]0第 0 天无股票收益 0dp[0][1]-inf第 0 天不可能持有股票负无穷非法状态● 最终答案dp[n][0]最后一天一定不持有股票卖出才兑现利润​​​​​​​【算法代码】#include bits/stdc.h using namespace std; const int inf0x3f3f3f3f; const int N1e55; int dp[N][2]; int a[N]; int main() { int n; cinn; for(int i1; in; i) { cina[i]; } dp[0][0]0, dp[0][1]-inf; for(int i1; in; i) { 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]); } coutdp[n][0]endl; return 0; } /* in: 6 7 1 5 3 6 4 out: 7 */【参考文献】https://www.acwing.com/solution/content/38975/