题目描述

给定一个长度为 $N$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格，再给定一个非负整数 $f$，表示交易股票的手续费用。

设计一个算法来计算你所能获取的最大利润。

你可以无限次地完成交易，但是你每次交易都需要支付手续费。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式

第一行包含两个整数 $N$ 和 $f$，分别表示数组的长度以及每笔交易的手续费用。

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

输出格式

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

数据范围

$1 \leq N \leq 10^5$
$1 \leq f \leq 10^4$

输入样例

6 2
1 3 2 8 4 9

输出样例：

8

样例解释

在第 $1$ 天（股票价格 $=$ $1$）的时候买入，在第 $4$ 天（股票价格 $=$ $8$）的时候卖出，这笔交易所能获得利润 $= 8-1-2 = 5$。随后，在第 $5$ 天（股票价格 $=$ $4$）的时候买入，在第 $6$ 天 （股票价格 $=$ $9$）的时候卖出，这笔交易所能获得利润 $= 9-4-2 = 3 $。共得利润 $5+3 = 8$。

这题感觉比三四五都简单些。

同样，令dp[0/1][i]表示只考虑前i支股票，当前 无/有 股票的最大收益

在第 $i$ 天时，我们需要根据第 $i−1$ 天的状态来更新 $dp[0/1][i]$ 的值。

对于 $dp[0][i]$，有：

1. 保持不变。 $dp[0][i] = dp[0][i-1]$
2. 卖出股票。 $dp[0][i] = dp[1][i-1] + data[i] - f$

即$dp[0][i] = max(dp[0][i-1], dp[1][i-1] + data[i] - f)$

对于 $dp[1][i]$，有：

1. 保持不变。 $dp[1][i] = dp[1][i-1]$
2. 买入股票。 $dp[1][i] = dp[0][i-1] - data[i]$

即$dp[1][i] = max(dp[1][i-1], dp[0][i-1] - data[i])$

时间复杂度：$O(n)$
空间复杂度：$O(n)$

C++ 代码1

#include <iostream>

const int N=100010;

int n,f;
int data[N];
int dp[2][N];

int main()
{
    scanf("%d %d\n",&n,&f);
    for(int i=1;i<=n;i++)
        scanf("%d",&data[i]);
    dp[1][1]=-data[1];
    for(int i=2;i<=n;i++)
    {
        dp[0][i]=std::max(dp[0][i-1],data[i]+dp[1][i-1]-f);
        dp[1][i]=std::max(dp[1][i-1],dp[0][i-1]-data[i]);
    }
    std::cout<<dp[0][n];
    return 0;
}

我们在计算这两个状态转移方程时，并不需要存每天的股价与最大收入，只需要记录第 $i-1$ 天的最大收入与第 $i$ 天的股价即可。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

C++ 代码2

#include <iostream>

int n,f;
int data;
int dp0,dp1;

int main()
{
    scanf("%d %d\n%d",&n,&f,&data);
    dp1=-data;
    for(int i=2;i<=n;i++)
    {
        scanf(" %d",&data);
        dp0=std::max(dp0,dp1+data-f);
        dp1=std::max(dp1,dp0-data);
    }
    printf("%d",dp0);
    return 0;
}