描述:

给一些列数字,表示每条股票的价格,如果可以买卖一次(不能同一天买和卖),求最大利益(即差最大)。

其他三道问题是,如果能买卖无限次,买卖两次,买卖k次。

题一:

实质是求后面一个数减前一个数的最大差值。

维护一个最小值,和当前最大值。只需遍历一次,空间也是常数。

int maxProfit(vector<int>& prices) {
if (prices.size() < )
return ;
int min_ = prices[];
int ret = ; for (int i = ; i < prices.size(); i++) {
ret = max(ret, prices[i] - min_);
min_ = min(min_, prices[i]);
}
return ret;
}

题二:

只要是后一个数比前一个大,都增。

int maxProfit(vector<int>& prices) {
if (prices.size() < )
return ; int ret = ;
for (int i = ; i < prices.size() - ; i++) {
ret += max(prices[i + ] - prices[i], );
}
return ret;
}

题三:

可进行两次操作。

其中一个思路,可以关注分界点,可以枚举分界点,求左右两边的最优操作,在LeetCode会超时,显然,复杂度n^2。

思考下优化,我们可以计算每个点的最大值,左边不用重复计算,每次分界点往左移,都像题一那样计算最大值即可;

      而右边,其实可以反向计算一遍,但是,右边改成求最小值。

      最后加起来即可。

int maxProfit(vector<int>& prices) {
int size = prices.size();
if (size < )
return ;
int* left = new int[size]{};
int* right = new int[size]{};
int ret = ; int lmin = prices[];
int lmax = ;
for (int i = ; i < size; i++) {
lmax = max(lmax, prices[i] - lmin);
left[i] = lmax;
lmin = min(lmin, prices[i]);
} int rmin = ;
int rmax = prices[size - ];
for (int i = size - ; i >= ; i--) {
rmin = min(rmin, prices[i] - rmax);
right[i] = -rmin;
rmax = max(rmax, prices[i]);
} for (int i = ; i < size - ; i++) {
ret = max(ret, left[i] + right[i + ]);
}
return max(ret, left[size - ]);
}

思路二:

int maxProfit(vector<int>& prices) {

    int n = prices.size();
if(n==) return ;
int sell1 = , sell2 = , buy1 = INT_MIN, buy2 = INT_MIN; for(int i =; i<n; i++)
{
buy1 = max(buy1, -prices[i]);
sell1 = max(sell1, prices[i]+buy1);
buy2 = max(buy2, sell1-prices[i]);
sell2 = max(sell2, prices[i]+buy2);
}
return sell2;
}

题四:

动态规划:

其中diff表示今天和昨天的差。

global[i][j] = max(local[i][j], global[i-1][j])

local[i][j] = max(global[i-1][j-1] + max(diff,0), local[i-1][j] + diff)

local[i][j]表示最后一次卖出在今天的最大利益,局部最优。

global[i][j]表示全局最优。

第一条式子:要么在今天卖出最优,要么前一天的全局最优。

第二条式子:前者为之前的全局最优加上最后一次交易在今天。

        注意diff,我们要的是不大于j的交易次数;

        如果i - 1天还持有,则i天卖出,共j - 1次操作;如果i-1天不持有,则i - 1天买入,i天卖出,共j次操作。

      后者为i - 1天卖出加上今天diff,表示i - 1天还持有,加上今天的。

int maxProfit(int k, vector<int>& prices) {
if (prices.size() < ) return ; int days = prices.size();
if (k >= days) return maxProfit2(prices); auto local = vector<vector<int> >(days, vector<int>(k + ));
auto global = vector<vector<int> >(days, vector<int>(k + )); for (int i = ; i < days ; i++) {
int diff = prices[i] - prices[i - ]; for (int j = ; j <= k; j++) {
local[i][j] = max(global[i - ][j - ], local[i - ][j] + diff);
global[i][j] = max(global[i - ][j], local[i][j]);
}
} return global[days - ][k];
} int maxProfit2(vector<int>& prices) {
int maxProfit = ; for (int i = ; i < prices.size(); i++) {
if (prices[i] > prices[i - ]) {
maxProfit += prices[i] - prices[i - ];
}
} return maxProfit;
}

类似题三的做法:

int maxProfit(int k, vector<int>& prices) {

    int n = prices.size();

    if(k>n/)
{
int buy = INT_MIN, sell = ;
for(int i=; i<n; i++)
{
buy = max(buy, sell-prices[i]);
sell = max(sell, buy+prices[i]);
}
return sell;
} vector<int> sell(k+, );
vector<int> buy(k+, ); for(int i=; i<=k; i++) buy[i] = INT_MIN; for(int i=; i<n; i++)
{
for(int j=; j<k+; j++)
{ buy[j] = max(buy[j], sell[j-]-prices[i]);
sell[j] = max(sell[j], buy[j]+prices[i]); }
}
return sell[k];
}
05-01 01:54
查看更多