the DP translation as my understanding is as following


  • 0
    B
    • the objective is to get max profit with the last status of no share in hand:
      
    •      a serious of operations end up with sell or cooldown.
      
    •      ... ..., pre 2 day,      pre 1 day,   last day
      
    •                                            sell
      
    •                                sell        cooldown
      
    •              sell              coodwon     nothing happen after cooldown
      
    •              ... ...
      
    •      but sell depends buy or 'nothing happen after buy' happen before it.
      
    •      and 'cooldown' need sell happen just 1 day before it
      
    •      and 'nothing happen after cooldown' need cooldown happen before it.
      
    •      total relation as:
      
    •          buy -(next 1 or n days) -> sell
      
    •          sell -(next day)-> cooldown
      
    •          cooldown -(next 1 or n days) -> buy
      
    • all possible operation on day i and result status:
      
    •      buy                             ->  1 share in hand
      
    •      nothing happen after buy        ->  1 share in hand
      
    •      sell                            ->  0 share in hand
      
    •      cooldown                        ->  0 share in hand
      
    •      nothing happen after cooldown   ->  0 share in hand
      
    • so max profit of 0 share on be last day:
      
    •      max(
      
    •          1 max profit of 'sell' happen on last day,
      
    •          2 max profit of 'cooldown' happen on last day,
      
    •          3 max profit of 'nothing happen after cooldown' happen on last day,
      
    •      }
      
    •      try make it simple:
      
    • all possible operation on day i and result status:
      
    •      endByBuy                        ->  1 share in hand
      
    •      sell                            ->  0 share in hand
      
    •      endByCooldown                   ->  0 share in hand
      
    • so max profit of 0 share on be last day:
      
    •      max(
      
    •          1 max profit of 'sell' happen on last day,
      
    •          2 max profit of 'endByCooldown' happen on last day,
      
    •      }
      
    • DP translations of max profix: drawing a picture will be easy to understand.
      
    •          max_endBysell[last] = max_endByBuy[last - 1] + prices[last];
      
    •          max_endByCooldown[last] = Math.max(max_endByCooldown[last - 1], max_endBysell[last - 1]);
      
    •     then: max_endByBuy[i] = Math.max(max_endByCooldown[i - 1] - prices[i], max_endByBuy[i - 1]);
      

    and the code


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.