跳到主要内容

Best Time to Buy and Sell Stock III

描述

Say you have an array for which the i-th 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).

分析

设状态f(i),表示区间[0,i](0in1)[0,i](0 \leq i \leq n-1)的最大利润,状态g(i),表示区间[i,n1](0in1)[i, n-1](0 \leq i \leq n-1)的最大利润,则最终答案为max{f(i)+g(i)},0in1\max\left\{f(i)+g(i)\right\},0 \leq i \leq n-1

允许在一天内买进又卖出,相当于不交易,因为题目的规定是最多两次,而不是一定要两次。

将原数组变成差分数组,本题也可以看做是最大m子段和,m=2,参考代码:https://gist.github.com/soulmachine/5906637

代码

// Best Time to Buy and Sell Stock III
// 时间复杂度O(n),空间复杂度O(n)
public class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) return 0;

final int n = prices.length;
int[] f = new int[n];
int[] g = new int[n];

for (int i = 1, valley = prices[0]; i < n; ++i) {
valley = Math.min(valley, prices[i]);
f[i] = Math.max(f[i - 1], prices[i] - valley);
}

for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) {
peak = Math.max(peak, prices[i]);
g[i] = Math.max(g[i], peak - prices[i]);
}

int max_profit = 0;
for (int i = 0; i < n; ++i)
max_profit = Math.max(max_profit, f[i] + g[i]);

return max_profit;
}
}

相关题目