SHARE
TWEET

Untitled

a guest Apr 22nd, 2019 98 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2. class Solution {
  3.  
  4.     /**
  5.      * @param Integer $k
  6.      * @param Integer[] $prices
  7.      * @return Integer
  8.      */
  9.     function maxProfit($k, $prices) {
  10.         $res = 0;
  11.         $len = count($prices);
  12.         if($k > $len){
  13.             for($i = 0; $i < $len - 1; $i++)
  14.             {
  15.                 $h = $prices[$i + 1] - $prices[$i];
  16.                 if($h > 0){
  17.                     $res += $h;
  18.                 }
  19.             }
  20.            
  21.             return $res;
  22.         }
  23.        
  24.         $buy = array_fill(0, $k+1, PHP_INT_MIN);
  25.         $sell = array_fill(0, $k+1, 0);
  26.        
  27.         for($i = 0; $i < $len; $i++)
  28.         {
  29.             for($j = $k; $j > 0; $j--)
  30.             {
  31.                 $sell[$j] = max($sell[$j], $buy[$j] + $prices[$i]);
  32.                 $buy[$j] = max($buy[$j], $sell[$j - 1] - $prices[$i]);
  33.             }
  34.         }
  35.         return $sell[$k];
  36.     }
  37. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top