2020-03-11 18:19:00
问题描述:
给出一个股票 n 天的价格, 每天最多只能进行一次交易, 可以选择买入一支股票或卖出一支股票或放弃交易, 输出能够达到的最大利润值
样例
样例 1:
给出 `a = [1,2,10,9]`, 返回 `16`
输入:
[1,2,10,9]
输出:
16
解释:
你可以在第一天和第二天买入股票, 第三天和第四天卖出
利润:-1-2+10+9 = 16
样例 2:
给出 `a = [9,5,9,10,5]`, 返回 `5`
输入:
[9,5,9,10,5]
输出:
5
解释:
你可以在第 2 天买入, 第 4 天卖出
利润:-5 + 10 = 5
注意事项
1 ≤ n ≤ 10000
问题求解:
之前 Stock Problems 里有遇到过 k 交易, 每次手里至多有 1 个股票的问题; 这里是一个扩展题, 交易数量不限, 而且手里的股票数量也不限.
网络上有人发了 dfs 的解, 自己也尝试过使用 dfs 来做, 但是是会 TLE 的, 使用 dfs 不做剪枝操作理论的时间复杂度是指数级别的.
正确的解法是使用 dp.
dp[i][j] : 前 i 天结束手里有 j 个股票所能达到的最大值
对于 dp[i][j] 就有三种策略, 不做交易 dp[i - 1][j], 买入 dp[i - 1][j - 1] - prices[i - 1], 卖出 dp[i - 1][j + 1] + prices[i - 1].
边界条件再完善一下就可以了.
本题直接开 dp[n + 1][n + 1] 会 MLE, 需要使用滚动数组来降低空间复杂度才能 AC. 另外, 感觉题目的 test case 比较水, 没有达到 10000 的量级, 上述的解的时间复杂度约为 O(n ^ 2), 理论上是过不了大数据的. 尝试提交了一下, 还是 AC 了.
时间复杂度 :O(n ^ 2).
- public int getAns(int[] a) {
- int n = a.length;
- int[] dp = new int[n + 1];
- int[] presum = new int[n];
- presum[0] = a[0];
- for (int i = 1; i <n; i++) presum[i] = presum[i - 1] + a[i];
- dp[0] = 0;
- for (int i = 1; i <= n; i++) dp[i] = Integer.MIN_VALUE;
- for (int i = 1; i <= n; i++) {
- int[] prev = Arrays.copyOf(dp, n);
- dp[0] = Math.max(prev[0], prev[1] + a[i - 1]);
- dp[i] = -presum[i - 1];
- dp[i - 1] = Math.max(dp[i - 1], i>= 2 ? prev[i - 2] - a[i - 1] : Integer.MIN_VALUE);
- for (int j = 1; j <= i - 2; j++) {
- dp[j] = Math.max(Math.max(prev[j], prev[j - 1] - a[i - 1]), prev[j + 1] + a[i - 1]);
- }
- }
- return dp[0];
- }
来源: http://www.bubuko.com/infodetail-3457064.html