本章算法知识点

题目：买卖股票的最佳时机
题目类型：数组动态规划
题目难度：比较困难

买卖股票的最佳时机算法题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 105

Java解题代码思路

 public static void main(String[] args ){
        int[] a={1,2,3,4,5};
        int b=maxProfit(a);
        System.out.println( b );
    }


        public static int maxProfit(int[] prices) {
            int result = 0;
            if (prices.length == 0) {
                return result;
            }
            int firstDealSell;
            int secondDealSell;
            for (secondDealSell = prices.length - 1; secondDealSell > 0; secondDealSell--) {
                if (prices[secondDealSell - 1] < prices[secondDealSell]) {
                    break;
                }
            }
            for (firstDealSell = 1; firstDealSell < prices.length; firstDealSell++) {
                while (firstDealSell + 1 < prices.length && prices[firstDealSell + 1] >= prices[firstDealSell]) {
                    firstDealSell++;
                }
                int result1 = maxProfit(prices, 0, firstDealSell);
                int result2 = maxProfit(prices, firstDealSell + 1, secondDealSell);
                if (result1 + result2 > result) {
                    result = result1 + result2;
                }
            }
            return result;
        }
        private static int maxProfit(int[] prices, int left, int right) {
            int result = 0;
            if (right - left < 1) {
                return result;
            }
            int minPrice = prices[left];
            for (int i = left + 1; i <= right; i++) {
                result = Math.max(result, prices[i] - minPrice);
                minPrice = Math.min(minPrice, prices[i]);
            }
            return result;
        }

算法的其他知识点

观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣，可以发现它们的花瓣数为斐波那契数：3，5，8，13，21，…，如图上图所示。

树木在生长过程中往往需要一些“休息”时间，供自身生长，而后才能萌发新枝。所以，一株树苗在一段时间（如一年）后长出一个新枝；第二年新枝“休息”，老枝依旧萌发；此后，老枝与“休息”过一年的枝同时萌发，当年新生的枝在次年“休息”。这样，一株树木各个年份的枝丫数便构成斐波那契数列，这一规律就是生物学上著名的“鲁德维格定律”。

这些植物懂得斐波那契数列吗？并非如此，它们只是按照自然规律才进化成这样。这似乎是植物排列种子的“优化方式”——能使所有种子具有相近的大小却又疏密得当，不至于在圆心处挤太多的种子而在圆周处却又很稀疏。叶子的生长方式也是如此，对于许多植物来说，每片叶子从中轴附近生长出来，为了在生长过程中一直都能最佳地利用空间（要考虑到叶子是一片一片逐渐生长出来，而不是一下子同时出现的），每片叶子和前一片叶子之间的角度应该是222.5°，这个角度被称为“黄金角度”，因为它和整个圆周（360°）之比是黄金分割数0.618的倒数，而这种生长方式就导致斐波那契螺旋的产生。向日葵的种子排列形成的斐波那契螺旋有时能达到89条，甚至144条。1992年，两位法国科学家通过对花瓣形成的过程进行计算机仿真实验，证实了在系统保持最低能量的状态下，花朵会以斐波那契数列的规律长出花瓣。

斐波那契数列起源于兔子数列，这个现实中的例子让我们真切地感到数学源于生活。在生活中，我们需要不断地透过现象发现数学问题，而不是为了学习而学习。我们学习的目的是满足自己对世界的好奇心，如果你能怀着这样一颗好奇心，或许世界会因你而不同！当斐波那契通过兔子繁殖告诉我们这种数学问题的本质——随着数列项的增加，前一项与后一项之比越来越逼近黄金分割数0.618时，我被彻底震撼，因为数学可以表达美，这是数学令我们叹为观止的地方。当数学创造出更多的奇迹时，我们会发现数学在本质上是可以回归自然的，这样的事例让我们感受到数学的美，就像黄金分割、斐波那契数列，它们如同大自然中的一朵朵小花，散发着智慧的芳香……