美文网首页
面试题63(剑指offer)--股票的最大利润

面试题63(剑指offer)--股票的最大利润

作者: Tiramisu_b630 | 来源:发表于2019-08-15 09:28 被阅读0次

    题目:

    假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可获得的最大利润是多少?

    示例:

        一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果
        我们能在价格为5的时候买入并在价格为16时卖出,则能获得最大的利润为11.
    

    解法:

        /**
         * 某天能获得最大利润取当天价格减去以前最小价格的值和
         * 当天之前能获得的最大利润两者中的最大值。
         * 比如{7,1,5,3,6,8},dp[5]=Max(8-1,6)=7
         * @param prices
         * @return
         */
        public static int maxProfit(int[] prices){
            if (prices == null||prices.length==0) {
                return 0;
            }
            int length = prices.length;
            if (length==1){
                return 0;
            }
            int[] dp=new int[length];//dp[i]表示到第i天的最大利润
            int min=prices[0];//记录当天之前的最小值
            dp[0]=0;
            for (int i = 1; i <length ; i++) {
                dp[i]=Math.max(dp[i-1],prices[i]-min);
                if (prices[i]<min){
                    min=prices[i];
                }
            }
            return dp[length-1];
        }
    

    相关文章

      网友评论

          本文标题:面试题63(剑指offer)--股票的最大利润

          本文链接:https://www.haomeiwen.com/subject/ezunjctx.html