123. 买卖股票的最佳时机 III(leetcode)

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

这一题较难,难点是状态比较多,需要考虑两笔交易,则共5个状态需要被记录,用当前是否持有股票来划分子集进行计算

class Solution {public int maxProfit(int[] prices) {// 由于此题可以完成两笔交易,因此不只是只有一次持有和不持有,有两次,即四个状态+未交易过共5种状态// 因此一天可以有五种状态子集,f[i][0~4],0表示未交易过,1表示第一次持有2表示第一次不持有...// f[i][0]=f[i-1][0] ,直接转移即可,没有操作// f[i][1]=max(f[i-1][1],f[i-1][0]-prices[i])// f[i][2]=max(f[i-1][2],f[i-1][1]+prices[i])// f[i][3]=max(f[i-1][3],f[i-1][2]-prices[i])// f[i][4]=max(f[i-1][4],f[i-1][3]+prices[i])int[][] f=new int[prices.length+1][5];f[1][0]=0;f[1][1]=-prices[0];f[1][2]=0;f[1][3]=-prices[0];f[1][4]=0;for(int i=2;i<=prices.length;i++){f[i][0]=f[i-1][0];f[i][1]=Math.max(f[i-1][1],f[i-1][0]-prices[i-1]);f[i][2]=Math.max(f[i-1][2],f[i-1][1]+prices[i-1]);f[i][3]=Math.max(f[i-1][3],f[i-1][2]-prices[i-1]);f[i][4]=Math.max(f[i-1][4],f[i-1][3]+prices[i-1]);}return f[prices.length][4];   //最终状态是这个表达式,实际可能第一次卖出就达到最大值了,即f[prices.length][2],但是f[prices.length][4]是最大的集合,是包含f[prices.length]// 用更加通俗的道理:即第一次卖出达到最大了,可以再买,再买一次,也是最大值}   
}

最后的返回值,如同官方题解说的这样