leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0188.cpp (422B)

      1 class Solution {
      2   public:
      3     int maxProfit(const int k, const vector<int> &prices) const {
      4         vector<int> cost(k + 1, INT_MAX), profit(k + 1, 0);
      5 
      6         for (const int price : prices) {
      7             for (int i = 1; i <= k; i++) {
      8                 cost[i] = min(cost[i], price - profit[i - 1]);
      9                 profit[i] = max(profit[i], price - cost[i]);
     10             }
     11         }
     12 
     13         return profit[k];
     14     }
     15 };