剑指 Offer 63. 股票的最大利润
在解答算法题时注意特殊情况,比如给定的数组为空数组,有多次我都没考虑这种特殊情况,导致出错。回到这题上来,这是一道动态规划题,需要明白每天利润的最大值是从前一天利润的最大值和今天买股票的收益中去一个较大的值,然后一直循环到最后一天。别的关于动态规划的思路不多讲,因为思路这东西只可意会,不便于言说。代码如下:
class Solution { public: int maxProfit(vector<int>& prices) { if(prices.size()==0)return 0; vector<int>dp(prices.size(),0); dp[0]=0; int mymin=prices[0]; for(int i=1;i<prices.size();i++){ mymin=mymin>prices[i]? prices[i]:mymin; dp[i]=max(dp[i-1], prices[i]-mymin); cout<<dp[i]<<" "; } return *max_element(dp.begin(),dp.end()); } };