题解 | #买卖股票的最好时机(一)#
买卖股票的最好时机(一)
https://www.nowcoder.com/practice/351b87e53d0d44928f4de9b6217d36bb
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> prices;
int tmp = 0;
for(int i = 0; i < n; i++){
cin >> tmp;
prices.push_back(tmp);
}
//分析
//1.前一天持有股票：
//1.1 继续持有，不需要操作
//1.2 抛售股票 dp[i - 1][1] -> dp[i][0]
//2.前一天没有股票
//2.1 继续不持，不需要操作
//2.2 持有股票 dp[i - 1][0] -> dp[i][1]
int dp[n ][2]; //dp[i][0]表示不持有股票， dp[i][1]表示持有股票
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < n; i++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], -prices[i]);
}
cout << dp[n - 1][0] << endl;
return 0;
}
查看19道真题和解析
