刷题记录
*121. 买卖股票的最佳时机
贪心
找左侧最小值、右侧最大值（与最小值求差最大），求差即为最大利润。
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
// c++
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
int low=prices[0];
for(int i=0; i<prices.size(); i++){
low = min(low, prices[i]);
result = max(result, prices[i]-low);
}
return result;
}
};
*动态规划
// c++
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(2, vector<int>(2, 0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i=1; i<prices.size(); i++){
dp[i%2][0] = max(dp[(i-1)%2][0], -prices[i]);
dp[i%2][1] = max(dp[(i-1)%2][1], prices[i]+dp[(i-1)%2][0]);
}
int len = prices.size();
return dp[(len-1)%2][1];
}
};
122. 买卖股票的最佳时机 II
贪心
遍历价格列表，取记录最低价和当前价格比较取最小的赋值为新的最低价。
若当前价格卖出可以盈利则在当天卖出，同时再在当天买入，继续向后找最低价格。
tips: 题目提到可以在同一天进行买入和卖出，因此可以在当天卖出后再买入。
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
// c++
class Solution {
public:
int maxProfit(vector<int>& prices) {
int low = INT_MAX;
int res = 0;
for(int i=0; i<prices.size(); i++){
low = min(low, prices[i]);
if(prices[i]-low>0){
res += prices[i]-low;
low = prices[i];
}
}
return res;
}
};
*动态规划
和上题思路类似，上一题只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]。
本题可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。
第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即：dp[i - 1][1] - prices[i]。
// c++
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(2, vector<int>(2, 0));
dp[0][0] -= prices[0];
dp[0][1] = 0;
for(int i=1; i<prices.size(); i++){
dp[i%2][0] = max(dp[(i-1)%2][0], dp[(i-1)%2][1]-prices[i]);
dp[i%2][1] = max(dp[(i-1)%2][1], dp[(i-1)%2][0]+prices[i]);
}
int len = prices.size();
return max(dp[(len-1)%2][0], dp[(len-1)%2][1]);
}
};
*123. 买卖股票的最佳时机 III
一共四种状态，第一次买入/持有、第一次卖出/不持有、第二次买入/持有、第二次卖出/不持有。
分配四列来记录这四种状态，dp[i][j]是指在第i天的第j个状态时的最大利润。
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
// c++
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
// 不操作
dp[0][0] = 0;
// 第一次买入/持有
dp[0][1] = -prices[0];
// 第一次卖出/不持有
dp[0][2] = 0;
// 第二次买入/持有
dp[0][3] = -prices[0];
// 第二次卖出/不持有
dp[0][4] = 0;
for(int i=1; i<prices.size(); i++){
// dp[i][0] = 0;
dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1]);
dp[i][2] = max(dp[i-1][1]+prices[i], dp[i-1][2]);
dp[i][3] = max(dp[i-1][2]-prices[i], dp[i-1][3]);
dp[i][4] = max(dp[i-1][3]+prices[i], dp[i-1][4]);
}
int len=prices.size()-1;
return dp[len][4];
}
};