• API
• FAQ
• Tools
• Archive
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;
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.

Top