Say you have an array for which the?ith?element is the price of a given stock on day?i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

思路：變相的求最大子數組，是算法導論上的例題，書上用分治法做的。

若prices=[1,4,2,8,1]，每兩數相減所得的利潤，即頭一天買入，第二天賣出。

profit=[0,3,-2,6,-7],可以看到第一天買入，最后一天賣出的profit為3+(-2)+6+(-7)=0

代碼：

class Solution { public:int maxProfit(vector<int> &prices) {int len=prices.size();int res=0;int temp=0;if(len==0) return res;vector<int> profit(len,0);vector<int> dp(len,0);for(int i=0;i<len;++i){if(i==0) {profit[i]=0;continue;}profit[i]=prices[i]-prices[i-1];}dp[0]=profit[0];for(int i=1;i<len;++i){dp[i]=max(dp[i-1]+profit[i],profit[i]);if(dp[i]>res)res=dp[i];}return res;} };

?

轉載于:https://www.cnblogs.com/fightformylife/p/4190202.html

總結

以上是生活随笔為你收集整理的Best Time to Buy and Sell Stock(动态规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。