频道栏目
首页 > 考试 > 其他 > 正文

Leetcode 188. Best Time to Buy and Sell Stock IV (Hard) (cpp)

2016-12-29 10:46:00      个评论    来源:闷声大发财  
收藏   我要投稿

Leetcode 188. Best Time to Buy and Sell Stock IV (Hard)(cpp)

Tag: Dynamic Programming

Difficulty: Hard

/*

188. Best Time to Buy and Sell Stock IV (Hard)

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

*/
class Solution {
public:
	int maxProfit(int k, vector& prices) {
		if (prices.size() < 2) {
			return 0;
		}
		int res = 0;
		if (k >= prices.size() / 2) {
			for (int i = 1; i < prices.size(); i++) {
				if (prices[i] > prices[i - 1]) {
					res += prices[i] - prices[i - 1];
				}
			}
		}
		else {
			vector cur(k + 1), glo(k + 1);
			for (int i = 0; i < prices.size() - 1; i++) {
				int increase = prices[i + 1] - prices[i];
				for (int j = k; j >= 1; j--) {
					cur[j] = max(glo[j - 1] + max(increase, 0), cur[j] + increase);
					glo[j] = max(glo[j], cur[j]);
				}
			}
			res = glo.back();
		}
		return res;
	}
};

 

\

相关TAG标签 Leetcode 编程题
上一篇:[Leetcode] 20. Valid Parentheses 解题报告
下一篇:leetcode434
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站