Jump to content
IPS Community Suite 简体中文
Sign in to follow this  
ipscn

MaxStockProfit

Recommended Posts

在Udemy的视频教程 Learning Algorithms In JavaScript From Scratch 中的第十六讲,有个例子:给定某一支股票在一段儿时间内每天的价格,计算可能的最大收益。视频教程的讲师给出的算法存在些问题,计算出来的,并不是可能的最大收益,这里给出更好的算法。

实例背景和原始算法

假设某一支股票,在一段儿时间内,每天的价格如下所示:

let arr = [32,46,26,38,40,48,42]

计算出股民可能的最大盈利。

视频的讲师给出的算法是这样的:

function maxStockProfit(arr){

  //初始值为0,表示没有收益
  let maxProfit = 0;
  //买入价格
  let buyPrice = 0;
  //卖出价格
  let sellPrice = 0;
  //是否改变买入价格
  let  changeBuyPrice = true;
  let len = arr.length;

  for(let i=0;i<len;i++){
    if(changeBuyPrice){
      buyPrice = arr[i];
    }
    sellPrice = arr[i+1];
    if(buyPrice>sellPrice){
      changeBuyPrice = true;
    }else{
      changeBuyPrice = false;
      let tempProfit = sellPrice- buyPrice;
      if(tempProfit>maxProfit){
          maxProfit = tempProfit;
      }
    }
  }

  return maxProfit;

}

使用这个算法计算并输出:

console.log(console.log(maxStockProfit( arr ));

得出的结果是22,那个视频的讲师也比较认同这个结果,可是实际上,这段时间内的最大收益,应该是36才对,具体操作如下:

在这天买入: 0 ,在这天卖出:1
在这天买入: 2 ,在这天卖出:5

第一次:买入价格是32,卖出价格是46,收益14;

第二次:买入价格是26,卖出价格是48,收益22;

以上两次操作实际收益为 14+22=36,没有比这个收益更大的收益了,所以,36是这段时间内,这只股票可能的最大收益。

算法优化

优化后的算法是:

//更加实用的股票最大收益算法。
function stockBuySell(arr,show){

  let maxProfit = 0;
  let n = arr.length;
  let count = 0;   
  let i= 0;
  //买入,卖出方案构成的数组
  let sol = [];

  if (n == 1){
    return [];
  }


  while (i < n-1){
    while ((i < n-1) && (arr[i+1] <= arr[i])){
      i++;
    }
    if (i == n-1){
      break;
    }
    sol[count] = {};
    sol[count].buyOn = i++;
    while ((i < n) && (arr[i] >= arr[i-1])){
      i++;
    }

    sol[count].sellOn = i-1;
    count++;
  }


  if (count == 0){
      show && console.log("看起来不太可能盈利");
  } else {
    for (let i = 0; i < count; i++){
      show && console.log("在这天买入: "+ sol[i].buyOn+" ,在这天卖出:"+ sol[i].sellOn);
      maxProfit += arr[sol[i].sellOn]-arr[sol[i].buyOn]
    }
  }
 
  return {sol:sol, maxProfit:maxProfit};
}

用它进行计算:

console.log(stockBuySell( arr ));

得到的输出是:

{ sol: [ { buyOn: 0, sellOn: 1 }, { buyOn: 2, sellOn: 5 } ], maxProfit: 36 }

上述输出中的 sol 是买入卖出的解决方案, maxProfit 表示这段时间这支股票的最大收益值。

问题出在哪儿?

读者自己想一下吧!看你能不能给出答案!

 

 

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×