[芝麻信用怎么关闭]939

标题：

给定一个数组prices，它的第i个元素prices[i]表明一支给定股票第i天的价格。

你只能挑选某一天买入这只股票，并挑选在未来的某一个不同的日子卖出该股票。规划一个算法来核算你所能获取的最大赢利。

回来你能够从这笔买卖中获取的最大赢利。假如你不能获取任何赢利，回来0。

示例：

输入：[7,1,5,3,6,4]

输出：5

解说：在第2天（股票价格=1）的时分买入，在第5天（股票价格=6）的时分卖出，最大赢利=6-1=5。

留意赢利不能是7-1=6,由于卖出价格需求大于买入价格；一起，你不能在买入前卖出股票。

思路：

动态规划

dp[i]：截止第i天的最大赢利

第i天可执行的操作：不做任何操作、买入股票、卖出股票

对应的dp[i]:dp[i-1]、-price[i]、price[i]-min_price

状况搬运公式:dp[i]=max(dp[i-1],-price[i],price[i]-min_price)

=max(dp[i-1],price[i]-min_price)

该思路的完成见代码一。

调查该思路的状况搬运公式，可知：后一个dp的值只依靠前一个dp的值，一切能够不运用dp数组，而是保护一个变量来记载dp的值，然后进一步优化空间运用，优化后的版别见代码二。

代码一：

classSolution{\npublic:\nintmaxProfit(vector<int>&prices){\nintn=prices.size();\nvector<int>dp(n,0);\n\nintmin_price=prices[0];\ndp[0]=0;\nfor(inti=1;i<n;i++)\n{\ndp[i]=max(dp[i-1],prices[i]-min_price);\nmin_price=min(min_price,prices[i]);\n}\n\nreturndp.back();\n}\n};\t

代码二：

classSolution{\npublic:\nintmaxProfit(vector<int>&prices){\nintn=prices.size();\nintmin_price=prices[0];\nintdp=0;\nfor(inti=1;i<n;i++)\n{\ndp=max(dp,prices[i]-min_price);\nmin_price=min(min_price,prices[i]);\n}\n\nreturndp;\n}\n};