image.png

可以在leetcode找原题
记录一下解法

第一问

// 股票问题第一问，有一个数组，每个数字表示当前时刻的股票价值。假设目前你只能进行一次交易（买入，卖出），求最大收益？
public class stock1 {
    public static int bestTime1(int[] arr){
        // 边界处理，如果arr是空的，最大收益0元
        if (arr==null || arr.length==0){
            return 0;
        }
        // 如何确定最佳交易？首先想到，如果要在第一个点卖出，最佳收益是多少？，第二个点，...第i个点收益个是多少，最佳收益必在其中。
        int profit = 0;
        int min = arr[0];
        for (int i=1;i<arr.length;i++){
            min = Math.min(min,arr[i]);
            profit = Math.max(arr[i]-min,profit);
        }
        return profit;
    }

    public static void main(String[] args) {
        int[] prices = new int[]{5,1,6,3,4,8,5};
        System.out.println(bestTime1(prices));
    }
}

第二问：

// 股票问题2，同样的一个数组，表示的意义和问题一一样，此时可以进行无数次交易，求最好的收益？
public class stock2 {
    public static int bestTime2(int[] arr){
        if (arr==null || arr.length==0){
            return 0;
        }
        // 如何才是最大的收益，即在最低点买入，最高点卖出。
        // 如果我们把这些数字在图上用线段连起来，就是发现在求每一个坡度的高度累加和
        // 而每个坡高都可以看成每个小间隔的累加和，所以只要后边的比我大，我就累加，比我小，我就回到0
        int profit = 0;
        for (int i=1;i<arr.length;i++){
            profit += arr[i]>arr[i-1]?arr[i]-arr[i-1]:0;
        }
        return profit;
    }

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

第四问

// 股票问题四 还是这养的一组股票数据，但是你只能进行最多K次交易。求最大的收益？
// 股票问题三问的是最多2次交易，股票问题是问的是K次，所以直接将K次的，2次的参数变一下就好了。
public class stock4 {
    public static int bestTime4(int[] arr,int K){
        if (arr==null || arr.length==0){
            return 0;
        }
        // 首先明确一下用动态规划的思路可以解，通过画出二维矩阵x轴是数组长度，y轴是交易次数。
        // 分析要给格子怎么赋予含义才能得到问题的解？我们要求的是在N数组长度进行最大不超过K次交易获得收益最大。
        // 那每一个格子的表示含义就应该是在x（x<=N）长度的数组最多y（y<=K）次交易的时候,最大收益。
        // 分析得出，右下角的方格其实就是我们要求得点。
        // 继续分析，第一行和第一列有什么独特之处？
        // 第一行表示（这里我画的x是往下，y是往右）N长度为0，那么第一行不管K等于多少肯定都是0
        // 第一列表示K=0 一次交易都没有。说明第一列也是0的收益
        // 我们再考虑下有没有什么可以优化的点或者遗漏的地方？
        // 其实我们可以优先判断如果N/2<=K 说明其实等同于可以进行无限次交易
        int N = arr.length;
        if (K>=N/2){
            // 走股票问题二那一套逻辑
            return allTrans(arr);
        }
        // 这里K为什么要+1？因为比如你最多能进行2次交易，其实你是有0次，1次，2次三种选择的，所以要加1.
        int [][] dp = new int[N][K+1];
        // 为什么外层循坏是从K开始？我们现在直到要求的右下角那个位置的值，
        // 所以要么我们是么情况一：大循坏从左往右，小循环从上往下，
        // 要么情况二就是大循环从上往下，小循坏从左往右。
        // 分析一下可行性？假设我们是情况二，那假设现在我们大循环在N=100的位置，然后K的从0开始递增。似乎没有操作性
        // 但是如果是情况一：我们可以分析出来 假设现在K=4，我们N一路往下递增。假设现在N=100了
        // 那么K=4，N=100这个值怎么依赖什么呢？即dp[100][4]的值
        // 这时候假设两种情况，
        // 1.如果在100的位置，最后第4次用不上，是不是等同于dp[100][3],dp[100][3]的值是多少我们不需要考虑，
        // 因为根据我们这种循环，之前肯定已经得到了dp[100][3]的值，才轮得到计算dp[100][4]。
        // 2.如果在100位置，需要用到这第四次交易。即在100的位置是一个卖出的值。
        // 那可以分解成前三次交易的最大收益-之后的一个买入值+最后卖出的值
        // best表示上一次交易产生的最大收益-最后一次买入价，那么dp[i][j]在最后一个值要卖出的时候其实有i+1种情况
        // 举个例子（只关注最后最后一个值是要卖出的情况）
        // dp[100][4] = dp[100][3]-arr[100]
        // 也可能      = dp[99][3]-arr[99]
        // 一直到      = dp[0][3]-arr[0],在这里面取一个最大值=>best
        // 然后拿best+arr[i]就是dp[i][j]的值
        // 分析出了普遍位置，我们从最开始的位置找到一个可以往下传递的依赖。即可以通过求dp[1][j]的best,往下层层推
        for (int j=1;j<=K;j++){
            // 先分析dp[1][j]
            int p1 = dp[0][j];
            int best = Math.max(dp[1][j-1]-arr[1],dp[0][j]-arr[0]);
            dp[1][j] = Math.max(p1,best+arr[1]);
            for (int i=2;i<N;i++){
                p1 = dp[i-1][j];
                best = Math.max(dp[i][j-1]-arr[i],best);
                dp[i][j] = Math.max(best+arr[i],p1);
            }
        }
        // N-1 是因为N是长度，从0开始计算
        return dp[N-1][K];
    }

    private static int allTrans(int[] arr) {
        int profit = 0;
        for (int i=1;i<arr.length;i++){
            profit += arr[i]>arr[i-1]?arr[i]-arr[i-1]:0;
        }
        return profit;
    }
}

第五问

// 股票问题5 有冷却时间 即在一次交易完成后必须间隔1天后才可以开始下一次交易，可以进行无限次交易
public class stock5 {
    public static int bestTime5(int[] arr){
        if (arr==null || arr.length==0){
            return 0;
        }
        // 我们先定义一个数组buy[i]这个考虑的是在第i个位置是否是进行购买操作
        // buy[i]表示前面的最大收益-最后一次购买值
        // 如果i位置没有买入  那么其实buy[i]是等于buy[i-1]的。
        // 如果 i位置是买入，那么buy[i] = sell[i-2]-arr[i]
        // sell[i]同理,sell[i]表示到i位置目前最大收益，
        // 如果i不是卖出位置，sell[i] = sell[i-1]
        // 否则sell[i] = buy[i-1]+arr[i]

        // 考虑普通情况找尝试
        int[] buy = new int[arr.length];
        int[] sell = new int[arr.length];
        // buy[0] = -arr[0]   sell[0] = 0
        buy[1] = Math.max(-arr[0],-arr[1]);
        sell[1] = Math.max(0,arr[1]-arr[0]);
        for (int i=2;i<arr.length;i++){
            buy[i] = Math.max(buy[i-1],sell[i-2]-arr[i]);
            sell[i] = Math.max(sell[i-1],buy[i-1]+arr[i]);
        }
        return sell[arr.length-1];
    }

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

第六问

// 股票问题6 可以进行无限次交易，但是每次交易后都必须支付一定费用。
public class stock6 {
    public static int bestTime6(int[] arr, int fee){
        if (arr==null || arr.length==0 || fee<0){
            return 0;
        }
        // 最开始的时候买和卖的情况定义一下
        // 我们假设扣除fee在buy的时候进行
        int bestBuy = -arr[0]-fee;
        int bestSell = 0;

        for (int i=1;i<arr.length;i++){
            int curBuy = bestSell - arr[i] -fee;
            int curSell = bestBuy + arr[i];
            bestBuy = Math.max(bestBuy,curBuy);
            bestSell = Math.max(bestSell,curSell);
        }
        return bestSell;
    }
}