Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

Input: [1,2,3,0,2]Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell] 使用动态规划，时间复杂度为O(n),空间复杂度为O(n)

1 public int maxProfit(int[] prices) {
   //dp mytip 2         if(null==prices||0==prices.length){ 3             return 0; 4         } 5         int[][] states = new int[prices.length+1][2];//0表示此刻无股票，1表示此刻有股票，数组长度为prices.length+1是放置i-2溢出 6         states[1][1]= -prices[0];//第一天买股票 7         for(int i=2;i<=prices.length;i++){ 8             states[i][0]=Math.max(states[i-1][0],states[i-1][1]+prices[i-1]);//第i天无股票是第i-1天无股票和第i天卖股票的最大值 9             states[i][1]=Math.max(states[i-2][0]-prices[i-1],states[i-1][1]);//第i天有股票是第i-1天有股票和第i天买股票的最大值10         }11         return states[prices.length][0];12         13     }

 

优化空间复杂度为O(1)

1 public int maxProfit(int[] prices) {
   //dp mytip 2         if(null==prices||0==prices.length){ 3             return 0; 4         } 5         int preStock = 0;//只需要保持前两天的结果，将数组优化为变量，相当于states[i-2][1] 6         int stock =-prices[0];//states[i-1][1] 7         int preNoStock =0;//states[i-2][0] 8         int noStock =0;//states[i-1][0] 9         int[][] states = new int[prices.length+1][2];10         11         for(int i=1;i

 

相关题

买卖股票的最佳时间1 LeetCode121 

买卖股票的最佳时间2 LeetCode122 

买卖股票的最佳时间3 LeetCode123 

买卖股票的最佳时间4 LeetCode188 

买卖股票的最佳时间交易费 LeetCode714