D109 122. Best Time to Buy and Sell Stock II

题目链接

122. Best Time to Buy and Sell Stock II

题目分析

给定一个数组，代表商品价格。从给定的数组中，计算通过买卖能获得的最大收益。只有卖出才能再买入。

思路

一开始以为是获取最小值右边的最大值去卖出。

后来发现规律，是在价格拐点进行买入卖出操作。

即，先单调递减后单调递增时买入，先单调递增后单调递减时卖出。

最终代码

<?php
class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $profit = 0;
        $buyIndex = -1;
        $days = count($prices);
        $increasing = ($prices[0]<$prices[1]);
        if($increasing){
            $buyIndex = 0;
        }
        for($i=1; $i<$days; $i++){
            //if is increasing perviously
            if($increasing){
                //but starts to decrease
                //than its time to sell
                if($prices[$i]>$prices[$i+1]){
                    if($buyIndex != -1 ){
                        $profit += $prices[$i]-$prices[$buyIndex];
                    }
                    $buyIndex = $i+1;
                    $increasing = false;
                }
            }
            else{ //decreasing
                //starts 
                if($prices[$i]<$prices[$i+1]){
                    $buyIndex = $i;
                    $increasing = true;
                }
            }
        }
        return $profit;
    }
}

我个人认为这个函数并没有使用很复杂的算法，但是只打败了28.36%。内存占用只打败了15.79%。有很大的改进空间。

若觉得本文章对你有用，欢迎用爱发电资助。