? 股票买卖这个算法话题可以说是在基础算法这一块是一个很有意思的存在了。题目稍微变一些或许就回要以完全不同的眼光去看待这个问题。话不多说，一起来看看...
给定一个数组 prices ，它的第?i 个元素?prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
输入：[7,1,5,3,6,4]
输出：5
思路分析：对数组的每一项都有一个确定的最大利润。获得的方式就是，用当前值减去之前出现的最小值。(当然这种股票买法肯定不可能了是吧)。因此就用两个变量来分别动态表示最小值minprice和最大利润max。遍历一遍数组就是不是就可以了呢？
var maxProfit = function(prices) {
let minprice=Number.MAX_SAFE_INTEGER
let max=0
for(let i=0;i<prices.length;i++){
if(prices[i]<minprice){
minprice=prices[i]
}else if(prices[i]-minprice>max){
max=prices[i]-minprice
}
}
return max
};?这其实就是类似双指针的思想了。
那假设你可以无限次地完成交易，但是你每笔交易都需要付手续费fee。并且如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
?很容易想到的是贪心算法，只要有我一次买入卖出的利润减去fee之后还有剩余那么我就赚了，事实上这样的思想可能并不会带来全局最优解，因为第二天还是递增的话那么买入卖出还得交出手续费。所以还得判断一下第二天是否还是递增的。
?
?
可以采用一个巧妙的思想：将手续费在买入的时候交出，而不是卖出。维护一个buy变量为prices[i]+fee，遍历数组并且更新buy为最小。另外假如prices[i]大于buy那么就可以获得利润，但是为了防止之后会有递增的prices[i]，因此此时buy更新为prices[i]，而不是prices[i]+fee。
var maxProfit = function(prices, fee) {
let buy=prices[0]+fee
let max=0
for(let i=1;i<prices.length;i++){
if(prices[i]+fee<buy){
buy=prices[i]+fee
}else if(prices[i]>buy){
max+=prices[i]-buy
//考虑到之后有prices[i]递增
buy=prices[i]
}
}
return max
}除此之外还可以用动态规划来解决。分析一下状态可以知道，第i+1天只有两种状态，手上有股票以及手上没有股票，所以定义一个二维数组。dp[i][0]代表手上没有股票时的最大收益。dp[i][1]代表手上有股票时的最大收益。
那么递归方程就很好写了，dp[i][0]可能是由于dp[i-1][0]，也可能是dp[i][0]+prices[i]-fee把股票卖了。两者取大值。
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)
同理可以得到：
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i])
边界条件的话就是dp[0][0]=0,dp[0][1]=-prices[0],可以得到代码：
var maxProfit = function(prices, fee) {
let dp=new Array(prices.length).fill(0).map(item=>new Array(2).fill(0))
dp[0][0]=0,dp[0][1]=-prices[0]
for(let i=1;i<prices.length;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i])
}
return Math.max(dp[prices.length-1][0],dp[prices.length-1][1])
};ok，继续修改题目...如果不考虑手续费怎么做呢？那就是只要相邻两项有正差值，那么就可以买入卖出，此时局部最优就是整体最优解，正儿八经的贪心算法。只需要遍历数组，比较前后的差值与0的关系就行。
var maxProfit = function(prices){
let result=0
for(let i=1;i<prices.length;i++){
result+=Math.max(0,prices[i]-prices[i-1])
}
return result
}还有一种变体，那么加入卖完股票后有一天的冷冻期呢？
这个·我就直接选择动态规划，分析可知，每一个天只会有三种状态。第一种状态是手上持有股票(用0表示)，第二种状态是处于冷冻期(用1表示)，第三种状态时处于冷冻期之外的非持有股票(用2表示)。所以，dp[i][0],dp[i][1],dp[i][2]分别代表三种状态下的最大利润。
分析状态方程可以知道：
dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][2]-prices[i])
dp[i][1] =?dp[i-1][0] ,?prices[i]
dp[i][2] = Math.max(dp[i-1][2] ,?dp[i-1][1])
第三步就是确定初始状态：
dp[0][0] = -prices[0],dp[0][0] = 0,dp[0][0] = 0
上代码：
var maxProfit = function(prices) {
let dp=new Array(prices.length).fill(0).map(item=>new Array(3).fill(0))
dp[0][0]=-prices[0]
dp[0][1]=0
dp[0][2]=0
for(let i=1;i<prices.length;i++){
//持有股票
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i])
//处于冷冻期，不持有股票
dp[i][1]=dp[i-1][0]+prices[i]
//不处于冷冻期，不持有股票
dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1])
}
return Math.max(dp[prices.length-1][1],dp[prices.length-1][2])
};以上就是关于股票题目的js分享，有贪心，有动态规划，以及类似双指针(争取一次性遍历数组)的思想了。仔细品味还是别有一番韵味，那么现在就有一个问题，是不是所有的算法到头来可以总结出一个元算法？就像宇宙物理里面的大一统理论呢？有待探索。