算法练习——买卖股票的最佳时机 III

2021年1月9日LeetCode每日一题为123. 买卖股票的最佳时机 III,这一题从题目上看通过最多两笔交易来求得最大利润,其本质就是要将所有收益可能给求出来,再选一个最好的,附上题解,这个题解非常详细。尝试一下使用递归,运用递归的思想将其分解为若干个子问题,那么我们的递归方法需要一个状态表示买入还是卖出,一个count表示交易的次数,以及当前交易的金额对应下标。下面附上看过题解后的练习代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public static int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
return max(prices, 0, 0, 0);
}

// 买入还是卖出还是不操作、第几次交易,这次交易的金额对应下标
public static int max(int[] prices, int status, int count, int index) {
if (index == prices.length || count >= 2) {
return 0;
}
int buy = 0, sell = 0, keep;
keep = max(prices, status, count, index + 1);
if (status == 0) {
buy = max(prices, 1, count, index + 1) - prices[index];
} else {
sell = max(prices, 0, count + 1, index + 1) + prices[index];
}
return Math.max(Math.max(buy, sell), keep);
}

}

这一题在开始只能想到可以使用递归来进行,但是对于递归的一些状态分析的不好,想了好久也没想出一个比较好的答案,最终只能求助题解,这里给出的题解从递归开始讲起,一直往上优化最终到动态规划,非常详细,也非常适合新手学习。在看过题解后,在回过来写了一遍,发现在这几个状态之间的递归方式是我没想到的,一直陷于怎么确定下一步的操作,由此可见递归思想仍然没有成为思考问题的主要思路,一种化大问题为小问题的思想,仍然需要坚持练习,希望今后面对这些问题我能够很轻松的写出一个递归来解决,再通过优化来降低时间复杂度,提高算法效率。