字数
763 字
阅读时间
4 分钟
121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II123. 买卖股票的最佳时机 III
题意
给一个数组表示股票的价格，你每天最多持有一支股票，总共可以买最多两只股然后卖出，问最大利润
思路1
针对只能买两支股票，首先找出如果只买一支的最大利润对应的范围
接下来有两种可能
- 第一种，
不处理，其他区间找 - 第二种，
内部不是递增的，分成两部分， - 第二种可以从[ans_i1,ans_i2]遍历，处理成对应下标左边最大和右边最小
这个思路可以画个折线图，比较好理解
代码1
CPP
class Solution
{
public:
int maxProfit(vector<int> &prices)
{
int n = prices.size();
int ans = 0;
int mx_prices = prices[n - 1];
int mx_i = n - 1;
int ans_i1 = -1, ans_i2 = -1;
for (int i = n - 2; i >= 0; i--)
{
if (mx_prices - prices[i] > ans)
{
ans_i1 = i;
ans_i2 = mx_i;
ans = mx_prices - prices[i];
}
if (prices[i] > mx_prices)
{
mx_i = i;
mx_prices = prices[i];
}
}
if (ans_i1 == ans_i2)
return 0;
// 第一种
mx_prices = prices[n - 1];
int ans1 = 0, ans2 = 0;
for (int i = n - 2; i >= ans_i2; i--)
{
mx_prices = max(mx_prices, prices[i]);
ans1 = max(ans1, mx_prices - prices[i]);
}
mx_prices = prices[ans_i1];
for (int i = ans_i1; i >= 0; i--)
{
mx_prices = max(mx_prices, prices[i]);
ans2 = max(ans2, mx_prices - prices[i]);
}
if (ans_i1 == ans_i2)
return ans + max(ans1, ans2);
// 第二种
vector<int> n_prices(prices.begin() + ans_i1, prices.begin() + ans_i2 + 1);
int nn = n_prices.size();
vector<int> l_mx(n_prices);
vector<int> r_mn(n_prices);
for (int i = 1; i < nn; i++)
l_mx[i] = max(l_mx[i], l_mx[i - 1]);
for (int i = nn - 2; i >= 0; i--)
r_mn[i] = min(r_mn[i], r_mn[i + 1]);
int ans3 = 0;
int Beg = n_prices[0], End = n_prices[nn - 1];
for (int i = 0; i < nn; i++)
ans3 = max(ans3, l_mx[i] - Beg + End - r_mn[i]);
return max(ans + max(ans1, ans2), ans3);
}
};思路2 动态规划
针对每一天的状态，有以下五种：
- 啥都没买
- 买了第一支股票还没卖
- 卖了第一支股票
- 买了第二支股票还没卖
- 卖了第二支股票
啥都没买不需要管，接下来用四个变量存储：
代码如下：
CPP
class Solution
{
public:
Solution(vector<int> p)
{
cout << maxProfit(p);
}
int maxProfit(vector<int> &prices)
{
int n = prices.size();
int buy1 = -1e9, sell1 = -1e9, buy2 = -1e9, sell2 = -1e9;
for (int i = 0; i < n; i++)
{
buy1 = max(buy1, -prices[i]);
sell1 = max(sell1, prices[i] + buy1);
buy2 = max(buy2, sell1 - prices[i]);
sell2 = max(sell2, prices[i] + buy2);
}
return sell2;
}
};但是如果不仅可以买两支股票呢
代码2
就是加了个buy和sell数组，不过我觉得其实可以用一个数组，不过两个数组好理解
没有测试例子，不确定k变大的时候有没有问题
CPP
int maxProfit2(vector<int> &prices)
{
int k = 2;
int n = prices.size();
// int buy1 = -1e9, sell1 = -1e9, buy2 = -1e9, sell2 = -1e9;
vector<int> buy(k + 1, -1e9), sell(k + 1, -1e9);
sell[0] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 1; j < k; j++)
{
buy[j] = max(buy[j], sell[j - 1] - prices[i]);
sell[j] = max(sell[j], prices[i] + buy[j]);
buy[j + 1] = max(buy[j + 1], sell[j] - prices[i]);
sell[j + 1] = max(sell[j + 1], buy[j + 1] + prices[i]);
}
}
return sell[k];
}贡献者
lulaalu