LeetCode160--最长递增子序列(L300)、最佳买卖股票时机含冷冻期(L309)

///给你一个整数组 nums ，找出严格递增子序列最长的长度。
//
// 子序列是从数组中衍生出来的序列，在不改变其他元素的顺序的情况下删除(或不删除)数组中的元素。例如[3、6、2、7] 是数组 [0，3，1，6，2，7] 的子序
//列。
//
//
// 示例 1：
//
//
//输入：nums = 101，18]
//输出：4
//解释:最长递增子序列 [2，3，7，101] 4 。
//
//
// 示例 2：
//
//
//输入：nums = [0，1，0，3，2
//输出：4
//
//
// 示例 3：
//
//
//输入：nums = 7、7、7、7、7
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 2500
// -104 <= nums[i] <= 104
//
//
//
//
// 进阶：
//
//
// 可以设计时间复杂度 O(n2) 解决方案吗？
// 您可以将算法的时间复杂度降低到 O(n log(n)) 吗?
//
// Related Topics 数组 二分查找 动态规划

方法一:动态规划
动态规划维护数组，保存nums[i]最长递增子序列的长度，因此我们可以写状态转移方程：
dp[i]=max(dp[j] 1),其中0<=j 所以只要我们的num[i]>num[j]您可以在现有的递增子序列中添加一个元素，然后我们可以遍历前面dp[j]然后取最大值加1
边界条件dp[0]=1

public int lengthOfLIS(int[] nums) { 
                 ///方法:采用动态规划方法，在这里维护dp是保存着以nums[i]最长递增子序列结尾的长度         if(nums == null || nums.length == 0){ 
                     return 0;         }         int[] dp = new int[nums.length];         dp[0] = 1;         int maxans = 1;         for (int i = 1; i < nums.length; i ) { 
                     dp[i] = 1;             for (int j = 0; j < i; j ) { 
                         if(nums[i] > nums[j]){ 
                             dp[i]= Math.max(dp[j] + 1, dp[i]);
                }
            }
            maxans = Math.max(dp[i], maxans);
        }
        return maxans;

方法二：采用贪心算法+二分查找法
贪心的思想主要就是当我们的子序列
新定义一个数组，dp[i]表示长度为i的上升子序列末尾的最小值。而且我们通过遍历数组，不断更新数组d，如果nums[i]>d[j]那么直接有d[j+1]=num[i]，如果nums[i] 这里需要注意的是最后d数组并不是我们得到的最长递增子序列数组，而只是维护了一种递增关系而已，反例如下：
以输入序列 [0, 8, 4, 12, 2] 为例：

• 第一步插入 0，d = [0]；
• 第二步插入 8，d = [0, 8]；
• 第三步插入 4，d = [0, 4]；
• 第四步插入 12，d = [0, 4, 12]；
• 第五步插入 2，d = [0, 2, 12]。

最终得到最大递增子序列长度为 3。

class Solution { 
        
    public int lengthOfLIS(int[] nums) { 
        
        int len = 1, n = nums.length;
        if (n == 0) { 
        
            return 0;
        }
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) { 
        
            if (nums[i] > d[len]) { 
        
                d[++len] = nums[i];
            } else { 
        
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) { 
        
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) { 
        
                        pos = mid;
                        l = mid + 1;
                    } else { 
        
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
}

//给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
//
// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
//
//
// 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
//
//
// 示例:
//
// 输入: [1,2,3,0,2]
//输出: 3
//解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
// Related Topics 数组 动态规划

这是一个稍微复杂亿点点的动态规划，但是理清关系就比较好解决，注释里都有了。

public int maxProfit(int[] prices) { 
        
        //分析一下一共有三种情况：持有股票，不持有股票且处于冷冻期，不持有股票且不处于冷冻期
        //这里说的处于冷冻期就是在第i天结束之后的下一天是冷冻期
        //分别用dp[i][0],dp[i][1],dp[i][2]
        //1.对于dp[i][0]有两种情况，即第i-1就已经对股票持有了，还有在第i天买入了新的股票
        //dp[i][0] = max(dp[i-1][0],dp[i-1][2] - prices[i])
        //2.对于dp[i][1]说明当天肯定有股票卖出并且前一天持有股票
        //dp[i][1] = dp[i-1][0] + prices[i];
        //3.对于dp[i][2],说明在当天没有任何的买入和卖出的操作，所以它还是有两种情况，即前一天就不属于冷冻期还有前一天就是冷冻期
        //dp[i][2] = max(dp[i-1][2],dp[i-1][1])
        //最后说一些边界条件
        //dp[0][0] = -prices[0]
        //dp[0][1] = 0
        //dp[0][2] = 0
        //最后我们输出的结果是Math.max(dp[n][1],dp[n][2])，因为最后一天持有股票肯定是没有任何意义的，也算不上收益
        int n = prices.length;
        if(n == 0){ 
        
            return 0;
        }
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        for (int i = 1; i < n; i++) { 
        
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2] - prices[i]);
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);
        }
        return Math.max(dp[n-1][1], dp[n-1][2]);
    }