aboutsummaryrefslogtreecommitdiff
path: root/buy_sell_stock.cpp
blob: 122ee2a019e5fb6675bf3fed94089af2c3718503 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "leetcode.h"

class Solution {
public:
  int maxProfit(int k, vector<int> &prices) {
    if (k == 0)
      return 0;
    if (prices.size() == 0 || prices.size() == 1)
      return 0;
    vvd dp(k + 1, vector<int>(prices.size()));
    for (int i = 0; i < dp.size(); i++) {
      for (int j = 0; j < dp[i].size(); j++) {
        if (i == 0 || j == 0)
          dp[i][j] = 0;
        else {
          int x, mx = INT_MIN;
          for (int k = 0; k < j; k++) {
            x = prices[j] - prices[k] + dp[i - 1][k];
            mx = max(x, mx);
          }
          dp[i][j] = max(dp[i][j - 1], mx);
        }
      }
    }
    return dp[dp.size() - 1][prices.size() - 1];
  }
};

int main() {
  Solution obj;
  int k = 2;
  vector<int> prices = {2, 4, 1};
  cout << obj.maxProfit(k, prices);
}