classSolution: """ @param k: an integer @param prices: a list of integer @return: an integer which is maximum profit """ defmaxProfit(self, k, prices): if prices isNoneorlen(prices) <= 1or k <= 0: return0
n = len(prices) # k >= prices.length / 2 ==> multiple transactions Stock II if k >= n / 2: profit_max = 0 for i in xrange(1, n): diff = prices[i] - prices[i - 1] if diff > 0: profit_max += diff return profit_max
f = [[0for i in xrange(k + 1)] for j in xrange(n + 1)] for j in xrange(1, k + 1): for i in xrange(1, n + 1): for x in xrange(0, i + 1): f[i][j] = max(f[i][j], f[x][j - 1] + self.profit(prices, x + 1, i))
return f[n][k]
# calculate the profit of prices(l, u) defprofit(self, prices, l, u): if l >= u: return0 valley = 2**31 - 1 profit_max = 0 for price in prices[l - 1:u]: profit_max = max(profit_max, price - valley) valley = min(valley, price) return profit_max
classSolution { public: /** * @param k: An integer * @param prices: Given an integer array * @return: Maximum profit */ intmaxProfit(int k, vector<int> &prices){ if (prices.size() <= 1 || k <= 0) return0;
int n = prices.size(); // k >= prices.length / 2 ==> multiple transactions Stock II if (k >= n / 2) { int profit_max = 0; for (int i = 1; i < n; ++i) { int diff = prices[i] - prices[i - 1]; if (diff > 0) { profit_max += diff; } } return profit_max; }
vector<vector<int> > f = vector<vector<int> >(n + 1, vector<int>(k + 1, 0)); for (int j = 1; j <= k; ++j) { for (int i = 1; i <= n; ++i) { for (int x = 0; x <= i; ++x) { f[i][j] = max(f[i][j], f[x][j - 1] + profit(prices, x + 1, i)); } } }
return f[n][k]; }
private: intprofit(vector<int> &prices, int l, int u){ if (l >= u) return0;
int valley = INT_MAX; int profit_max = 0; for (int i = l - 1; i < u; ++i) { profit_max = max(profit_max, prices[i] - valley); valley = min(valley, prices[i]); }