贪心算法解决买卖股票问题_stock贪心算法

问题描述：现在有一个数组，依次保存第1天、第2天.........到第n天的股票价格，例如{7,1,5,3,6,4}则表示第1天股票7元钱，第2天股票1元钱。。。现在你最多只能持有1股，每天买卖股票的次数不限，请问如何卖卖股票使得利润最大化

贪心算法的观点:如果我们用贪心算法来解决，就要找到局部最优解，然后再得到整体的最优解。我们可以从第一天的股票价钱出发，和第二天的对比，如果第二天比第一天价格更高了(稳赚)，就赶紧买进第1天的，然后第二天卖出。同理，到了第二天，我就和第三天的价格做对比，只要后一天的价格高于今天的，我就买进今天的股票，到后一天再卖出。赚到的钱依次相加，得到最大的利润。当然如果后一天的价格比今天的低，我们就不买。

时间复杂度：O（n)

实现代码：

public class Greedy {
    
    public static void main(String[] args) {
        //股票的每一天的价格数组
        int[] stock={7,1,5,3,6,4};
        //记录得到的利润
        int money=0;
        for(int i=0,len=stock.length-1;i<len;i++){
            //得到今天的股票价格
            int today=stock[i];
            //得到下一天的股票价格
            int tomorrow=stock[i+1];
            //贪心算法比较两天的价格，如果第二天大于第一天的价格，则买进第一天股票，第二天卖出
            if(tomorrow>today){
                //赚了这两天的差价
                money+=tomorrow-today;
            }
        }
        System.out.println(money);
    }

}