• 给定一个数组arr，从左到右表示昨天从早到晚股票的价格。作为一个事后诸葛亮，你想知道如果只做一次交易，且每次交易只买卖一股，返回能挣到的最大钱数

/**
 * 给定一个数组arr，从左到右表示昨天从早到晚股票的价格。作为一个事后诸葛亮，
 * 你想知道如果只做一次交易，且每次交易只买卖一股，返回能挣到的最大钱数
 */
public class BuyStock01 {
    public static int buyStock(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }

        // 每次来到i位置都都是一个卖出时机，在0~中找一个最小值点买入，i点卖出，
        // 每个位置都这样操作，答案比在其中
        int min  = arr[0];
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            // 更新0~i的最小值
            min = Math.min(min,arr[i]);
            res = Math.max(res,arr[i] - min);
        }

        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,4,3,5,6,7,8,9};
        System.out.println(buyStock(arr));
    }
}

• 给定一个数组arr，从左到右表示昨天从早到晚股票的价格,作为一个事后诸葛亮，你想知道如果随便交易，且每次交易只买卖一股，返回能挣到的最大钱数。

/**
 * 给定一个数组arr，从左到右表示昨天从早到晚股票的价格,作为一个事后诸葛亮，
 * 你想知道如果随便交易，且每次交易只买卖一股，返回能挣到的最大钱数。
 */
public class BuyStock02 {
    public static int buyStock(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int money = 0;
        int pre = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] > pre){
                money += arr[i] - pre;
            }
            pre = arr[i];
        }

        return money;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,4,3,5,7,6,9,8,10};
        System.out.println(buyStock(arr));
    }
}

• 给定一个数组arr，从左到右表示昨天从早到晚股票的价格

• 作为一个事后诸葛亮，你想知 道如果交易次数不超过K次，
• 且每次交易只买卖一股，返回能挣到的最大钱数

/**
 *给定一个数组arr，从左到右表示昨天从早到晚股票的价格
 *  * 作为一个事后诸葛亮，你想知 道如果交易次数不超过K次，
 *  * 且每次交易只买卖一股，返回能挣到的最大钱数
 */
public class BuyStock03 {
    public static int buyStock(int[] arr,int k){
        if(arr == null || arr.length == 0 || k < 2){
            return 0;
        }
        if(k > arr.length / 2){
            return  buyStock(arr);
        }

        int[][] dp = new int[arr.length][k+1];
        // 第一行全部是0，第一列全部是0
        // 求普遍位置dp[i][j]的值(含义0~i时间点随便交易，不超过j此的情况下最大钱数)
        // 1)、最后的交易不在i位置，那么dp[i][j] = dp[i-1][j]
        // 2)、最后的交易在i位置，且小贪心，i位置进行卖出操作，能取得最大值
        //     a.dp[i][j] = dp[i][j-1] + arr[i] - arr[i] ,0~i上随便交易，不超过j-1此的情况下，最后一次在i位置买，i位置卖
        //     b.dp[i][j] = dp[i-1][j-1] + arr[i] - arr[i-1]
        //     c.dp[i][j] = dp[i-2][j-1] + arr[i] = arr[i-2]
        //     ...
        //     可以推出 max{
        //                     dp[i][j] = dp[i][j-1] - arr[i],
        //                     dp[i][j] = dp[i-1][j-1] - arr[i-1],
        //                     dp[i][j] = dp[i-2][j-1] - arr[i-2],
        //                      ....
        //                } + arr[i]

        // 其实dp[i+1][j] = max{dp[i][j],max{dp[i+1][j-1] + arr[i+1] - arr[i+1],dp[i][j-1]-arr[i],...}+arr[i+1]}
        int res = 0;
        for (int j = 1; j <= k; j++) {
            // dp[0][j] = dp[0][j-1]  - arr[0] + arr[0]
            int t = dp[0][j-1] - arr[0];
            for (int i = 1; i < arr.length; i++) {
                // max{dp[1][j] = dp[0][j] ,max{ dp[1][j-1]  - arr[1],dp[0][j-1] - arr[0]}+arr[1]}
                t = Math.max(t,dp[i][j-1]-arr[i]);
                dp[i][j] = Math.max(dp[i-1][j],t+arr[i]);
                res = Math.max(dp[i][j],res);
            }
        }
        
        return res;
    }
    private static int buyStock(int[] arr){
        int money = 0;
        for (int i = 1; i < arr.length; i++) {
            money += Math.max(arr[i] - arr[i-1],0);
        }
        return money;
    }
    
}

• 给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个? 如果得到子序列A删除的位置与得到子序列B删除的位置不同，那么认为A和B就是不同的。
  【例子】
  S = "rabbbit", T = "rabbit"
  返回: 3
  是以下三个S的不同子序列，没有^的位置表示删除的位置，因为删除的位置不同，所以这三 个子序列是不一样的
  rabbbit
  I I I I II
  rabbbit
  I I I I II
  rabbbit
  I I I I II

/**
 * 给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个?
 * 如果得到子序列A删除的位置与得到子序列B删除的位置不同，那么认为A和B就是不同的。
 * 【例子】
 * S = "rabbbit", T = "rabbit"
 * 返回: 3
 * 是以下三个S的不同子序列，没有^的位置表示删除的位置，因为删除的位置不同，所以这三 个子序列是不一样的
 * rabbbit
 * I I   I I II
 * rabbbit
 * I I I   I II
 * rabbbit
 * I I I I   II
 */
public class MaxSubSeqNum {
    public static int  maxSubSeqNum(String s,String t){
        if((s == null && t == null) || ("".equals(s) && "".equals(t))){
            return 1;
        }
        if((s == null && t != null) || s.length() < t.length()){
            return 0;
        }
        // 定义dp[i][j] : s -> (0 ~ i) 子序列 随意删除 变换到，t -> (0 ~ j)的方法数
        // 第一行：s中第一个位置的字符随意删除，变成t中以0~j的字符，只有第一个位置如果相等有一种
        // 不相等0种，其余第一行位置全为0
        // 第一列，s中取0~i的字符，j中取第一个位置的字符有几种方法变到t,如果i位置和j位置相等
        // 加一种，如果i位置和j位置不相等，保留前面的种数。

        // 普遍位置：
        // 1.0~i随便删除，变为0~j但是不以i位置结尾 -> dp[i][j] = dp[i-1][j]
        // 2.0~i随便删除 且必须以i位置结尾(有条件i位置字符等于j位置字符才有这种可能) ->dp[i][j] = dp[i-1][j-1]

        // 大的过滤 s 字符的长度必须大于等于 t字符的长度，也就是说 右上半部分除了对角线都无效
        char[] sA = s.toCharArray();
        char[] tA = t.toCharArray();
        int[][] dp = new int[s.length()][t.length()];
        dp[0][0] = sA[0] == tA[0] ? 1 : 0;
        // dp[0][j] 其他不用填默认0
        // 列
        for (int i = 1; i < sA.length; i++) {
            dp[i][0] = sA[i] == tA[0] ?  dp[i-1][0] + 1 : dp[i-1][0];
        }

        // 普遍位置(可优化，右上半部分可以不要)
        for (int i = 1; i < sA.length; i++) {
            for (int j = 1; j < tA.length; j++) {
                dp[i][j] = dp[i-1][j] + (sA[i] == tA[j] ? dp[i-1][j-1] : 0);
            }
        }

        return dp[sA.length-1][tA.length-1];
    }

    public static void main(String[] args) {
        String s = "abcvcabc";
        String t = "abc";
        System.out.println(maxSubSeqNum(s,t));
    }
}