leecode 解题总结：188. Best Time to Buy and Sell Stock IV

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题: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).分析:此题必须计算至多k次交易的时候获取的最大利润。应该是动态规划。设dp[i][k]:表示第截止到第i天（不包含第i天）的时候，交易k次获取的最大利润最大利润来源于:1】前面i-1天就已经交易了k次，此时利用前i-1天的最大利润2】为前面第j天交易了k-1次，再进行一次：第j天买入，第i天卖出的交易，其中j属于[0 , i-1]dp[i][k] = max{ dp[i-1][k] , dp[j][k-1] + prices[i] - prices[j] }          = max { dp[i-1][k] , pricses[i] + max{ dp[j][k-1] - prices[j] }dp[0][k] = 0,表示第0天，无论交易多少次，利润为0dp[i][0] = 0,任意第i天，交易0次，利润肯定为0.最后遍历dp[i][j]，寻找最大的数值即可输入：5(数组元素个数) 4(最多允许交易的次数)1 2 3 -2 45 31 2 3 -2 45 21 2 3 -2 45 11 2 3 -2 45 21 -2 2 1 -31 2-11 2-1 -2输出:8886400报错:Runtime Error Message:terminate called after throwing an instance of 'std::bad_alloc'  what():  std::bad_alloc当k=1000000000时，我这个是三层循环，说明应该不能分配内存的关键:1避免k过大，内存溢出//这里如果超过1半数组元素个数，说明可以直接求两数之间正的差值作为利润		//应该是把出从较大到较小的这种情况屏蔽，比如 1 4 2,单调增的，则一次交易可涵盖多个		int sum = 0;		if(k >= size / 2)		{			for(int i = 1 ; i < size ; i++)			{				if(prices.at(i) > prices.at(i-1))				{					sum += ( prices.at(i) - prices.at(i-1) );				}			}			return sum;		}2 另外，如果只有一个价格，肯定没有利润，而不是返回正数*/class Solution {public:    int maxProfit(int k, vector<int>& prices) {		//如果只有一个价格，直接返回0，没有交易        if(prices.empty() || k <= 0 || 1 == prices.size())		{			return 0;		}				int size = prices.size();		//这里如果超过1半数组元素个数，说明可以直接求两数之间正的差值作为利润		//应该是把出从较大到较小的这种情况屏蔽，比如 1 4 2,单调增的，则一次交易可涵盖多个		int sum = 0;		if(k >= size / 2)		{			for(int i = 1 ; i < size ; i++)			{				if(prices.at(i) > prices.at(i-1))				{					sum += ( prices.at(i) - prices.at(i-1) );				}			}			return sum;		}				vector< vector<int> > dp( size + 1 , vector<int>(k + 1 , 0) ); //用vector溢出,改用new				int result = INT_MIN;		//dp[i][k] = max{ dp[i-1][k] , dp[j][k-1] + prices[i] - prices[j] } 		for(int p = 1 ; p <= k ; p++)		{			int maxTemp = dp[0][p-1] - prices.at(0);			for(int i = 1 ; i < size ; i++)			{				maxTemp = max(maxTemp , dp[i-1][p-1] - prices[i-1]);				dp[i][p] = max( dp[i-1][p] , prices[i] + maxTemp );				result = max(result , dp[i][p]);			}		}		return result;    }};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 int result;	 int maxTransactionTimes;	 while(cin >> num >> maxTransactionTimes )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 result = solution.maxProfit(maxTransactionTimes , nums);		 cout << result << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}