I:
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
只能买卖一次，求最大利益。一次遍历，求出当天-以前所有天最小值，并与已经记录的maxP比较，得到当天及以前天数的最大利益。
class Solution {
public:
int maxProfit(vector<int> &prices) {
if(prices.size()<=1)return 0;
int min=prices[0],maxP=0;
for(int i=1;i<prices.size();i++){
if(min>prices[i])min=prices[i];
if(maxP<prices[i]-min)maxP=prices[i]-min;
}
return maxP;
}
};
II:
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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock
before you buy again).
可以多次买卖，求最大利益。对于一组数据(2 3 6 8 7 5 2 8)，可以看出，数据要么是递增的(相等也算递增)，要么是递减的(此时的相等算递减)，于是，我们可以只考虑当天即明天的利益，如果明天的利益大于当天的利益，我们就当天买进明天卖出，这样必然是收益的。前面的“明天”为此时的今天，继续比较即可。如果当天利益小于下一天的利益，我们就不做操作。
由于可以多次操作，对于2 3 6 8 来说，我们2买进3卖出，3买进6卖出，6买进8卖出；和2买进8卖出是一样的收益。
class Solution {
public:
int maxProfit(vector<int> &prices) {
if(prices.size()<=1)return 0;
int maxP=0,temp;
for(int i=1;i<prices.size();i++){
temp=prices[i]-prices[i-1];
if(temp>0)maxP+=temp;
}
return maxP;
}
};
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.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
解法一：和解法二思路相似，这里，我们先计算出从第1天到第n天的每一天一次交易的最大值数组first[n]，然后计算出从第n天开始到第1天的每一天的一次交易最大值数组second[n+1](这里second[n]用来表示只交易一次的边界情况)，这样，对于maxP，为first[i]+second[i+1]中i从第一天到第n天的最大值。动态规划且思路相当巧妙。
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n=prices.size();
if(n<=1)return 0;
int *first = new int[n];
int *second = new int[n+1];
int min=prices[0],max=prices[n-1],maxP=0;
for(int i=1;i<prices.size();i++){
if(min>prices[i])min=prices[i];
if(maxP<prices[i]-min)maxP=prices[i]-min;
first[i]=maxP;
}
first[0]=0;maxP=0;
for(int i=n-2;i>=0;i--){
if(max<prices[i])max=prices[i];
if(maxP<max-prices[i])maxP=max-prices[i];
second[i]=maxP;
}
second[n-1]=0;maxP=0;second[n]=0;
for(int i=0;i<prices.size();i++){
if(maxP<first[i]+second[i+1])maxP=first[i]+second[i+1];
}
return maxP;
}
};
解法二：只能进行两次买卖。动态规划，我们假设i-1天及之前进行了一次交易，i天及之后进行一次交易，求i为多少时(i=1,2,...prices.size()-1)，两次交易的和最大。对于局部递增的序列，我们可以看为一个整体单元，即第一次交易一定发生在局部递增的最大值上，通过这个简单截枝，可以大大减少时间消耗。
class Solution {
public:
int maxProfitOfOne(vector<int> &prices,int beginIndex,int endIndex){
if(endIndex-beginIndex<=0)return 0;
int min=prices[beginIndex],maxP=0;
for(int i=beginIndex+1;i<=endIndex;i++){
if(min>prices[i])min=prices[i];
if(maxP<prices[i]-min)maxP=prices[i]-min;
}
return maxP;
}
int maxProfit(vector<int> &prices) {
if(prices.size()<=1)return 0;
int flag=1,maxP=0,temp;
for(int i=1;i<prices.size();i++){
if(flag==1){
if(prices[i]<prices[i-1]){
flag=-1;
temp=maxProfitOfOne(prices,0,i-1)+maxProfitOfOne(prices,i,prices.size()-1);
if(maxP<temp)maxP=temp;
}
}else if(flag==-1){
if(prices[i]>prices[i-1])flag=1;
}
}
if(maxP<maxProfitOfOne(prices,0,prices.size()-1))maxP=maxProfitOfOne(prices,0,prices.size()-1);
return maxP;
}
};