《leetCode》：Best Time to Buy and Sell Stock III

本文主要是介绍《leetCode》：Best Time to Buy and Sell Stock III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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 two transactions.

思路一：报超时错误

思路：分而治之，将prices分成两个部分，分别求这两部分的最大值，每个部分只允许存在一次交易；时间复杂度为O(n^2);

实现代码如下：


int getMaxProfitOneTransactions(int* prices, int pricesSize){if(prices==NULL||pricesSize<1){return 0;}int max=0;int buyPrice=prices[0];for(int i=0;i<pricesSize;i++){if(prices[i]<buyPrice){buyPrice=prices[i];}else{int profit=prices[i]-buyPrice;max=(max>profit)?max:profit;}}return max; 
}
int maxProfit(int* prices, int pricesSize) {if(prices==NULL||pricesSize<1){return 0;}int max=0;for(int i=0;i<pricesSize;i++){int maxPartOne_Two=getMaxProfitOneTransactions(prices,i)+getMaxProfitOneTransactions(prices+i,pricesSize-i);if(maxPartOne_Two>max){max=maxPartOne_Two;}}return max;
}

思路二

思路还是上面的思路，只是就空间来换取时间

/*
思路：分而治之，将prices分成两个部分，分别求这两部分的最大值 
解释：
首先，因为能买2次（第一次的卖可以和第二次的买在同一时间），但第二次的买不能在第一次的卖左边。
所以维护2个表，f1和f2，size都和prices一样大。
意义：
f1[i]表示 -- 截止到i下标为止，左边所做交易能够达到最大profit；
f2[i]表示 -- 从i下标开始，右边所做交易能够达到最大profit；
那么，对于f1 + f2，寻求最大即可。
*/int max(int a,int b){return (a>b)?a:b;
}int maxProfit(int* prices, int pricesSize) {if(prices==NULL||pricesSize<1){return 0;}int *f1=(int *)malloc(pricesSize*sizeof(int));int *f2=(int *)malloc(pricesSize*sizeof(int)); if(f1==NULL||f2==NULL){exit(EXIT_FAILURE);}//先看第一个交易f1[0]=0;int buyPriceMin=prices[0];for(int i=1;i<pricesSize;i++){if(prices[i]<buyPriceMin){buyPriceMin=prices[i];f1[i]=f1[i-1];//注意}else{int profit=prices[i]-buyPriceMin;f1[i]=max(f1[i-1],profit);}}//再看第二个交易，从右到左,寻找交易利润最大 f2[pricesSize-1]=0;int SellPriceMax=prices[pricesSize-1];for(int i=pricesSize-2;i>=0;i--){if(SellPriceMax<prices[i]){SellPriceMax=prices[i];f2[i]=f2[i+1];//注意}else{int profit=SellPriceMax-prices[i];f2[i]=max(f2[i+1],profit);}}//在f1+f2中寻找的最大值就是最大利润值int maxProfit=0;for(int i=0;i<pricesSize;i++){maxProfit=max(maxProfit,f1[i]+f2[i]);} return maxProfit;
}

上面的精简版本

int max(int a,int b){return (a>b)?a:b;
}
int min(int a,int b){return (a<b)?a:b;
}
int maxProfit(int* prices, int pricesSize) {if(prices==NULL||pricesSize<1){return 0;}int *f1=(int *)malloc(pricesSize*sizeof(int));int *f2=(int *)malloc(pricesSize*sizeof(int)); if(f1==NULL||f2==NULL){exit(EXIT_FAILURE);}//先看第一个交易f1[0]=0;int buyPriceMin=prices[0];for(int i=1;i<pricesSize;i++){buyPriceMin=min(buyPriceMin,prices[i]);f1[i]=max(f1[i-1],prices[i]-buyPriceMin);//用上面两行替换到下面被注释的部分
//      if(prices[i]<buyPriceMin){
//          buyPriceMin=prices[i];
//      }
//      else{
//          int profit=prices[i]-buyPriceMin;
//          f1[i]=max(f1[i-1],profit);
//      }}//再看第二个交易，从右到左,寻找交易利润最大 f2[pricesSize-1]=0;int SellPriceMax=prices[pricesSize-1];for(int i=pricesSize-2;i>=0;i--){SellPriceMax=max(SellPriceMax,prices[i]);f2[i]=max(f2[i+1],SellPriceMax-prices[i]);//用上面两行替换到下面被注释的部分
//      if(SellPriceMax<prices[i]){
//          SellPriceMax=prices[i];
//      }
//      else{
//          int profit=SellPriceMax-prices[i];
//          f2[i]=max(f2[i+1],profit);
//      }}//在f1+f2中寻找的最大值就是最大利润值int maxProfit=0;for(int i=0;i<pricesSize;i++){maxProfit=max(maxProfit,f1[i]+f2[i]);} return maxProfit;
}