题目描述
给定一个长度为 \(N\) 的数组，数组中的第 \(i\) 个数字表示一个给定股票在第 \(i\) 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
输入格式
第一行包含整数 \(N\)，表示数组长度。
第二行包含 \(N\) 个不大于 \(10^9\) 的正整数，表示完整的数组。
输出格式
输出一个整数，表示最大利润。
数据范围
$ 1 \le N \le 10^5 $,
输入样例1：
6
7 1 5 3 6 4
输出样例1：
5
输入样例2：
5
7 6 4 3 1
输出样例2：
0
样例解释
样例1：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为你不能在买入股票前卖出股票。
样例2：在这种情况下, 不进行任何交易, 所以最大利润为 0。
算法
(DP)
使用一个dp[x][y][z]数组来表示某种情况下的收益情况
x表示是第x天，y表示当前已经经过了第几次交易(交易以买进卖出两个操作为一次)
z使用0或者1来表示当前是否持有股票。
当前第i天交易0次并持有股票的状态 是从i - 1的交易0次持有股票转化而来
或者是从i - 1交易0次未持有股票买进了当前的股票转化而来。
dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][0][0] -prices[i]);
当前第i天交易1次并未持有股票的状态 是从i - 1交易1次未持有股票转化而来
或者是从i - 1交易1次持有股票以当天价格卖掉状态转化
dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][0][1] + prices[i]);
时间复杂度
dont know
空间复杂度
dont know
C++ 代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n == 1) return 0;
int f[n + 2][2][2];
f[0][0][1] = -prices[0];
f[0][0][0] = 0;
f[0][1][1] = -1e4;
f[0][1][0] = -1e4;
for(int i = 1; i < n; i ++)
{
f[i][1][1] = -1e4;
f[i][0][0] = f[i - 1][0][0];
f[i][0][1] = max(f[i - 1][0][1], f[i - 1][0][0] - prices[i]);
f[i][1][0] = max(f[i - 1][1][0], f[i - 1][0][1] + prices[i]);
}
return max(f[n - 1][1][0], 0);
}
};