题解 | #买卖股票的最好时机(一)#
买卖股票的最好时机(一)
https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec
2022.0818算法第36题买卖股票的最好时机(一)
这道题标注是简单，但是我真的没想出来，走弯路了
最优化的方式想不出来，需要先写复杂一点的。
1、状态矩阵
刚开始想的是第i天卖出的最大收益，但是后面做不出来了。
看了解析记录的是当前最小的股票价格，最大收益是计算得到的。
vector<int> dp(prices.size());2、初始值
这个还是比较简单的
dp[0]=prices[0]; int max_p=0;3、状态转移方程
记录之前的最小值，这样每次只需要和当前值进行比较就行，空间换时间。
for(int i=1;i<prices.size();i++){
if(prices[i]<dp[i-1]){
dp[i]=prices[i];
}
else
dp[i]=dp[i-1];
max_p=max(max_p,prices[i]-dp[i]);
}
以上代码可以进行优化，最小值可以使用一个变量进行存储，没必要使用数组。我觉着能想到上面那些是最重要的。
投递牛客等公司10个岗位 >
腾讯成长空间 449人发布
