SHARE
TWEET

Untitled

a guest Oct 22nd, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. static const auto s = []() {
  2.     std::ios::sync_with_stdio(false);
  3.     std::cin.tie(nullptr);
  4.     return nullptr;
  5. }();
  6.  
  7. class Solution {
  8. public:
  9.     int maxProfit(int k, vector<int>& prices) {
  10.         int high, low, max_diff, prev, current;
  11.         int len = prices.size();
  12.         int result = 0;
  13.         vector<vector<int>> dp(2, vector<int>(len+1, 0));
  14.         if(len == 0) return result;    
  15.         if(k > len/2) {
  16.             low = prices[0];
  17.             for(int i = 1; i < len; ++i) {
  18.                 if(prices[i] < prices[i-1]) {
  19.                     result += prices[i-1]-low;
  20.                     low = prices[i];
  21.                 }
  22.             }
  23.             result += prices[len-1] - low;
  24.         } else {
  25.             for(int i = 1; i <= k; ++i) {
  26.                 current = i & 1;
  27.                 prev = current ^ 1;
  28.                 for(int j = 0; j < len; ++j) {
  29.                     low = high = prices[j];
  30.                     max_diff = 0;
  31.                     dp[current][j] = 0;
  32.                     for(int g = j+1; g < len; ++g) {
  33.                         dp[current][j] = max(dp[current][j], dp[prev][g]+max_diff);
  34.                         high = max(high, prices[g]);
  35.                         if(prices[g] < low) low = high = prices[g];
  36.                         max_diff = max(max_diff, high-low);
  37.                     }
  38.                     dp[current][j] = max(dp[current][j], max_diff);
  39.                     result = max(result, dp[current][j]);
  40.                 }  
  41.             }
  42.         }
  43.         return result;    
  44.     }
  45. };
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