leetcode常规算法题复盘（第十二期）——摆动序列&买卖股票的最佳时机含手续费

 1 class Solution:
 2     def wiggleMaxLength(self, nums):
 3         if len(nums)<2:
 4             return len(nums)
 5         down_num = 1
 6         up_nums = 1
 7         down = nums[0]
 8         up = nums[0]
 9         i = 1
10         while i<len(nums):
11             print(nums)
12             print(up_nums)
13             print(up)
14             print(down_num)
15             print(down)
16             if nums[i]>nums[i-1]:
17                 up = nums[i]
18                 up_nums = down_num+1
19             elif nums[i]<nums[i-1]:
20                 down = nums[i]
21                 down_num = up_nums+1
22             i += 1
23         return max(up_nums,down_num)

 1 public class Solution {
 2     public int maxProfit(int [] prices,int fee) {
 3         int n = prices.length;
 4         int [][] dp = new int [n][2];
 5         dp[0][0] = 0;
 6         dp[0][1] = -prices[0];
 7         for(int i=1;i<n;i++) {
 8             dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]-fee);
 9             dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
10         }
11         return dp[n-1][0];
12     }
13 }

 1 public int wiggleMaxLength(int[] nums) {
 2     int down = 1, up = 1;
 3     for (int i = 1; i < nums.length; i++) {
 4         if (nums[i] > nums[i - 1])
 5             up = down + 1;
 6         else if (nums[i] < nums[i - 1])
 7             down = up + 1;
 8     }
 9     return nums.length == 0 ? 0 : Math.max(down, up);
10 }
11 
12 //作者：lgh18
13 //链接：https://leetcode-cn.com/problems/wiggle-subsequence/solution/tan-xin-si-lu-qing-xi-er-zheng-que-de-ti-jie-by-lg/
14 //来源：力扣（LeetCode）
15 //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 1 class Solution {
 2     public int maxProfit(int[] prices, int fee) {
 3         int n = prices.length;
 4         int[][] dp = new int[n][2];
 5         dp[0][0] = 0;
 6         dp[0][1] = -prices[0];
 7         for (int i = 1; i < n; i++) {
 8             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee); 
 9             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
10         }
11         return dp[n - 1][0];
12     }
13 }
14 
15 //作者：sweetiee
16 //链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/jian-dan-dpmiao-dong-gu-piao-mai-mai-by-tejdo/
17 //来源：力扣（LeetCode）
18 //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 1 class Solution {
 2     public int maxProfit(int[] prices, int fee) {
 3         int n = prices.length;
 4         int[] dp = new int[2];
 5         dp[0] = 0;
 6         dp[1] = -prices[0];
 7         for (int i = 1; i < n; i++) {
 8             int tmp = dp[0];
 9             dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee); 
10             dp[1] = Math.max(dp[1], tmp - prices[i]);
11         }
12         return dp[0];
13     }
14 }
15 
16 //作者：sweetiee
17 //链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/jian-dan-dpmiao-dong-gu-piao-mai-mai-by-tejdo/
18 //来源：力扣（LeetCode）
19 //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。