讨论/《初级算法》 - 买卖股票的最佳时机 II/
《初级算法》 - 买卖股票的最佳时机 II

新手,还不懂动态规划与贪心算法。凭借对数据的观察做出的判断。

步骤1:先从索引1开始找到一个数,要求他比它前一个数大,那么记住它前一个数的索引作为买入交易日。
步骤2:再继续判断这个数的后一位是否小于它,如果小于则表示它是当前的最高点,那么就可以作为卖出交易日。
步骤3:经过一次卖出得到一次收益并累加。然后把卖出的后一天作为新的买入交易日。
步骤4:重复步骤2,3,终止于最后一个数据判断完毕。

public int maxProfit(int[] prices) {
        //总收益
        int profit = 0;
        //买入时机
        int buyDay = 0;
        //卖出时机
        int sellDay = 1;
        while (sellDay < prices.length) {
                //判断买入时机
            if (prices[buyDay] > prices[sellDay]) {
                //找到买入时机
                buyDay = sellDay;
            } else {
                //找到卖出时机
                if (sellDay == prices.length - 1 || prices[sellDay] > prices[sellDay + 1]) {
                    profit += prices[sellDay] - prices[buyDay];
                    //把当前卖出时机的下一个交易日作为可能的买入时机,需要在下一轮进行判断是否符合买入时机
                   buyDay=++sellDay;
                }
            }
            //再次定位卖出时机到这次循环的第二个交易日
            sellDay++;
        }
        return profit;
    }

这个写法应该不具有普适规律,只是针对这个问题有意义。还是需要明白动态规划与贪心算法这些更加通用的思路。

展开全部 137 讨论