题目描述

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

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

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

样例

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

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int f[N][3];

int a[N];

int main()
{
    int n;

    cin >> n;

    memset(f,0xcf,sizeof f);
    memset(a,0x00,sizeof a);
    f[0][2] = 0;//很重要的一步，忘记写过不了
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    for(int i = 1; i <= n; i ++ )
    {
        f[i][0] = f[i-1][1]+a[i];
        f[i][1] = max(f[i-1][1],f[i-1][2]-a[i]);
        f[i][2] = max(f[i-1][2],f[i-1][0]);
    }

    int res = 0;

    for(int i = 1; i <= n ;i ++ )
    {
        res = max(f[i][0],res);
        res = max(f[i][2],res);
    }

    cout << res << endl;
    return 0;
}