题目描述

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
输入格式
第一行包含整数 N，表示数组长度。

第二行包含 N 个不超过 10000 的正整数，表示完整的数组。

输出格式
输出一个整数，表示最大利润。

数据范围
1≤N≤105

样例

输入样例：
5
1 2 3 0 2
输出样例：
3

算法1

(状态机) $O(n)$

//0表示冷冻期
//1表示持有股票
//2表示没有股票
f[i][0]=f[i-1][1]+mon[i];//卖出去，然后赚钱钱
f[i][1]=max(f[i-1][1],f[i-1][2]-mon[i]);//要么持有，要么买入
f[i][2]=max(f[i-1][2],f[i-1][0]);//从冷冻期中恢复过来和本来就木有

时间复杂度

O(n)

参考文献

50%没抄袭

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a,mon[N];
int f[N][3];
//0表示冷冻期
//1表示持有股票
//2表示没有股票
int main()
{
    scanf("%d",&a);
    for(int i=1;i<=a;i++) cin>>mon[i];
    memset(f,-0x3f,sizeof f);
    f[0][2]=0;
    for(int i=1;i<=a;i++)
    {
        f[i][0]=f[i-1][1]+mon[i];//卖出去，然后赚钱钱
        f[i][1]=max(f[i-1][1],f[i-1][2]-mon[i]);//要么持有，要么买入
        f[i][2]=max(f[i-1][2],f[i-1][0]);//从冷冻期中恢复过来和本来就木有
    }
    printf("%d",max(f[a][0],f[a][2]));
    return 0;
}