买卖股票的zui佳时机

1.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格，只能选择 某一天 买入这只股票，并选择在未来的某一个不同的日子 卖出该股票。设计一个算法来计算能获取的最大利润。

返回你可以从这笔交易中获取的最大利润，如果不能获取任何利润，返回 0 。

动态规划五部曲：

（1）dp数组及下标含义

dp[i][0]表示第i天持有股票所得现金，dp[i][1]表示第i天不有股票所得现金。

（2）确定递归函数

确定dp[i][0]：若第i-1天持有股票，dp[i][0] = dp[i-1][0]；若第i-1天未持有股票，dp[i][0] = -prices[i]。

确定dp[i][1]：若第i-1天持有股票，dp[i][1] = dp[i-1][0]+price[i]；若第i-1天未持有股票，dp[i][1] = dp[i-1][1]。

（3）dp数组初始化

dp[0][0] = -prices[0]，dp[0][1] = 0。

（4）遍历顺序

从前往后进行遍历。

（5）举例推导dp数组

实现代码如下：

//买卖股票的最佳时机
int maxProfit(vector& prices) {
	if(prices.size() == 0) return 0; 
	//1.dp数组及下标含义
	//dp[i][0]为第i天持有股票所得最多现金
	//dp[i][1]为第i天不持有股票所得最多现金
	vector> dp(prices.size(), vector (2));
	//3.dp数组初始化
	dp[0][0] = -prices[0];
	dp[0][1] = 0;
	
	//2.递归表达式 
	//4.遍历顺序
	for(int i = 1; i 
2.买卖股票的最佳时机II
 
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票），注意：不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 
该问题与上一个问题唯一的区别是股票可以买卖多次，在动规五部曲中主要区别体现在递推公式。
 
（2）确定递推函数
 
dp[i][0]表示第i天持有股票所得现金，dp[i][1]表示第i天不有股票所得现金。
 
确定dp[i][0]：若第i-1天持有股票，dp[i][0] = dp[i-1][0]；若第i-1天未持有股票，dp[i][0] = dp[i-1][1] - price[i]。
 
确定dp[i][1]：若第i-1天持有股票，dp[i][1] = dp[i-1][0]+price[i]；若第i-1天未持有股票，dp[i][1] = dp[i-1][1]。
 
实现代码如下：
 
int maxProfit(vector& prices) {
    int len = prices.size();
    vector> dp(len, vector(2, 0));
    dp[0][0] -= prices[0];
    dp[0][1] = 0;
    for (int i = 1; i < len; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
    }
    return dp[len - 1][1];
}
 
3.买卖股票的最佳时机III
 
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格，设计一个算法来计算所能获取的最大利润，最多可以完成两笔交易，注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 
该题的区别是整个过程中最多只能完成两次交易，思路一是遍历从0-i天最大收益，i+1-最后最大收益，加在一起为总收益，实现代码如下，但在一个测试用例中超时了。
 
//买卖股票的最佳时机III
//分成两次买卖 计算两次和的最大值 
int Profit(vector& prices, int start, int end) {
	//1.dp数组及下标含义
	//dp[i][0]表示第i天持有股票的最大收益
	//dp[i][1]表示第i天未持有股票的最大收益
	vector> dp(prices.size(), vector(2,0));
	//3.dp数组初始化
	dp[start][0] = -prices[start];
	dp[start][1] = 0;
	//2.确定递推数组
	//4.遍历顺序
	for(int i = start + 1; i<=end; i++) {
		dp[i][0] = max(dp[i-1][0], -prices[i]);
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);
	}
	//5.举例推导dp数组
	return dp[end][1];
}

int maxProfit(vector& prices) {
	if(prices.size() == 1) return 0;
	int result = 0;
	int result1 = 0;
	int result2 = 0;
	for(int i = 1; i 
接下来用动规五部曲：
 
每天可以对应五中操作：不参加操作，第一次持有，第一次不持有，第二次持有，第二次不持有。
 
（1）dp数组及下标含义
 
dp[i][j]表示第i天，第j种状态所得最大现金。
 
（2）确定递归函数
 
确定dp[i][1]：
 
第i天买入，dp[i][1] = dp[i-1][0] - prices[i]第i天没有操作，dp[i][1] = dp[i-1][1]
确定dp[i][2]：
 
第i天卖出，dp[i][2] = dp[i-1][1] + prices[i]第i天没有操作，dp[i][2] = dp[i-1][2]
确定dp[i][3]：
 
第i天买入，dp[i][3] = dp[i-1][2] - prices[i]第i天没有操作，dp[i][3] = dp[i-1][3]
确定dp[i][4]：
 
第i天卖出，dp[i][4] = dp[i-1][3] + prices[i]第i天没有操作，dp[i][4] = dp[i-1][4]
（3）dp数组初始化
 
dp[0][0] = 0，dp[0][1] = -price[0]，dp[0][2] = 0，dp[0][3] = -price[0]，dp[0][4] = 0。
 
（4）遍历顺序
 
从前往后进行遍历。
 
（5）举例推导dp数组
 
实现代码如下：
 
//动态规划
int maxProfit(vector& prices) {
	if(prices.size() == 1) return 0;
	//1.dp数组及下标含义
	vector> dp(prices.size(), vector(5,0));
	//3.dp数组初始化
	dp[0][1] = -prices[0];
	dp[0][3] = -prices[0];
	//2.确定递推数组
	//4.遍历顺序
	for(int i = 1; i 
4.买卖股票的最佳时机IV
 
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，设计一个算法来计算你所能获取的最大利润，最多可以完成 k 笔交易，注意：不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 
本题与上面的区别在于最多完成k笔交易，与上面类似，只不过每天有2k+1中状态，偶数就是不持有股票，奇数就是持有股票。实现代码如下：
 
//买卖股票的最佳时机IV
int maxProfit(int k, vector& prices) {
	//1.dp数组及下标含义
	//dp[i][j]为第i天在状态j的最大利润
	vector> dp(prices.size(), vector(2k+1, 0));
	//3.dp数组初始化
	for(int j = 1; j<=2k; j+=2) {
		dp[0][j] = -prices[0];
	} 
	//2.确定递推公式
	//4.确定遍历顺序
	for(int i = 1; i