D109 122. Best Time to Buy and Sell Stock II

Topic link

122. Best Time to Buy and Sell Stock II

Subject analysis

Given an array representing the price of goods. From a given array, calculate the maximum gain that can be made by buying or selling. You have to sell to buy again.

Train of thought

The initial thought is to get the maximum to the right of the minimum to sell.

Later found the law, is in the price inflection point to buy and sell operations.

Namely, buy after drab decrease first when drab increase, sell when drab increase after drab decrease first.

The final code

      
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; }}Copy the code

I personally don’t think this function uses a very complicated algorithm, but it only beats 28.36%. Memory usage beats only 15.79%. There’s a lot of room for improvement.

If you find this article useful, you are welcome to subsidize it with love.