题解 | #买卖股票的最好时机(一)#动态规划
买卖股票的最好时机(一)
https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec
动态规划直接求解（C语言）：
不难得到方程：最大利润Maxprofit=max(Maxprofit(前一天的最大利润)，prices[i]-min(此前的最小值))
求解步骤如下：
1.遍历数组，并保存最小值（动态更新）
2.比较前i天的利润，求最大值
3.输出最大利润
此算法时间复杂度=O(n)，空间复杂度=O(1)。
int maxProfit(int* prices, int pricesLen ) {
int i=0,j=0,profit=0,min=prices[0],Maxprofit=0;
for(i=1;i<pricesLen;i++){
//遍历过程中记录数组最小值
if(min>prices[i]){
min=prices[i];
}
//最大利润Maxprofit=max(Maxprofit(前一天的最大利润)，prices[i]-min(此前的最小值))
profit=prices[i]-min;
if(Maxprofit<profit){
Maxprofit=profit;
}
}
return Maxprofit;
}
查看5道真题和解析
