• 股票交易作为事后诸葛，交易次数不同时，返回挣到的最大钱数。

    问题描述：

    问题一：

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

    问题二：

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

    问题三：

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

    思想：

    问题一思想：

            我们遍历数组中的每一个位置i作为股票抛出的位置，i位置之前选取最小的位置作为股票的买入点，遍历完整个数组，取最大值即为最后答案。

    问题二思想：

            因为题意中已知交易次数不受限制，所以我们知道要想得到最大钱数，只要把数组中所有上浮的数值加起来就为最大钱数。

    问题三思想：

            交易次数受到限制，我们使用动态规划的思想进行解题。

            在解题前我们知道一个数学规律：若数组的长度为N，交易次数K是不会大于N/2的。若K若大于等于N/2，则该问题三等价于问题二。

            定义二维数组dp[i][j]，行表示数组中的每个值，列表示交易次数，二维数组含义是0~i时间点上随便交易，不超过j次的情况下取得的最大钱数。

            二维数组第一列表示0次交易取最大钱数，全部为0。二维数组第一列表示在0时间点上交易j次取得的最大钱数，全部为0。

            接下来我们分析普遍位置dp[i][j]。可以分为两种大类：

            1） 最后交易的位置不在i位置，那么dp[i][j] = dp[i-1][j]。

            2） 最后交易的位置在i位置，i位置时卖出操作时能取得最大值。又分为下面几种情况：

                    1> 0~i上随便交易，不过交易次数不能超过j-1次的情况下，最后在i位置上买，i位置上卖。【 dp[i][j] = dp[i][j-1] + arr[i] - arr[i] 】

                    2> 0~i-1上随便交易，不过交易次数不能超过j-1次的情况下，最后在i-1位置上买，i位置上卖。【 dp[i][j] = dp[i-1][j-1] + arr[i] - arr[i-1] 】

                    3> 0~i-2上随便交易，不过交易次数不能超过j-1次的情况下，最后在i-2位置上买，i位置上卖。【 dp[i][j] = dp[i-2][j-1] + arr[i] - arr[i-2] 】

                    .......

                    ii> 0~0上随便交易，不过交易次数不能超过j-1次的情况下，最后在0位置上买，i位置上卖。【 dp[i][j] = dp[i][j-1] + arr[i] - arr[0] 】

            到此全部分类完成，取出各种情况下的最大值为最后的结果。我们分析情况二中的迭代过程，我们会发现有重复的计算，因此我们可以对此进行优化。

            情况2）中

                    1>...ii>可以整合为：max{

                                                                    dp[i][j] = dp[i][j-1] - arr[i-1],

                                                                    dp[i][j] = dp[i-1][j-1] - arr[i-1],

                                                                    dp[i][j] = dp[i-2][j-1] - arr[i-1],

                                                                    ...

                                                                    dp[i][j] = dp[0][j-1] - arr[0],

                                                            }+ arr[i]。这个迭代结果可以提供给下一次计算直接使用。 

            我们也可以使用动态规划的空间压缩技术进行代码优化。

    代码：

    问题一代码：

    1.     public static int maxProfit(int[] prices) {
    2.         if (prices == null || prices.length == 0) {
    3.             return 0;
    4.         }
    5.         int min = prices[0];
    6.         int ans = 0;
    7.         for (int i = 0; i < prices.length; i++) {
    8.             min = Math.min(min, prices[i]);
    9.             ans = Math.max(ans, prices[i] - min);
    10.         }
    11.         return ans;
    12.     }
    13.  
    14.     public static int[] generateRandomArray(int maxSize, int maxValue) {
    15.         int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    16.         for (int i = 0; i < arr.length; i++) {
    17.             arr[i] = (int) ((maxValue + 1) * Math.random());
    18.         }
    19.         return arr;
    20.     }
    21.  
    22.     public static void main(String[] args) {
    23.         int maxSize = 20;
    24.         int maxValue = 20;
    25.         int testTime = 100000;
    26.         System.out.println("test begin!");
    27.         for (int i = 0; i < testTime; i++) {
    28.             int[] arr = generateRandomArray(maxSize, maxValue);
    29.             maxProfit(arr);
    30.         }
    31.         System.out.println("test end!");
    32.     }

    问题二代码：

    1.     public static int maxProfit(int[] prices) {
    2.         if (prices == null || prices.length == 0) {
    3.             return 0;
    4.         }
    5.         int money = 0;
    6.         int pre = prices[0];
    7.         for (int i = 1; i < prices.length; i++) {
    8.             if (prices[i] > pre) {
    9.                 money += prices[i] - pre;
    10.             }
    11.             pre = prices[i];
    12.         }
    13.         return money;
    14.     }
    15.  
    16.     public static int[] generateRandomArray(int maxSize, int maxValue) {
    17.         int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    18.         for (int i = 0; i < arr.length; i++) {
    19.             arr[i] = (int) ((maxValue + 1) * Math.random());
    20.         }
    21.         return arr;
    22.     }
    23.  
    24.     public static void main(String[] args) {
    25.         int maxSize = 20;
    26.         int maxValue = 20;
    27.         int testTime = 100000;
    28.         System.out.println("test begin!");
    29.         for (int i = 0; i < testTime; i++) {
    30.             int[] arr = generateRandomArray(maxSize, maxValue);
    31.             maxProfit(arr);
    32.         }
    33.         System.out.println("test end!");
    34.     }

    问题三代码：

            动态规划代码

    1.     public static int maxProfit1(int K, int[] prices) {
    2.         if (prices == null || prices.length == 0) {
    3.             return 0;
    4.         }
    5.         int N = prices.length;
    6.         if (K >= N / 2) {
    7.             return allTrans(prices);
    8.         }
    9.         int[][] dp = new int[N][K + 1];
    10.         int ans = 0;
    11.         //一列一列遍历
    12.         for (int j = 1; j <= K; j++) {
    13.             //dp[i][j] = dp[0][j]                    ---1)
    14.             //           dp[1][j-1]  - [1]  +  [1]   ---2)1>
    15.             //                      t       +  [1]  
    16.             //           dp[0][j-1]  - [0]  +  [1]   ---2)1>
    17.             //                      t       +  [1]   
    18.             //从第一列开始遍历，所以我么那必须先设置好t的值
    19.             int t = dp[0][j - 1] - prices[0];
    20.             for (int i = 1; i < N; i++) {
    21.                 int nextT = Math.max(t, dp[i][j - 1] - prices[i]);
    22.                 //情况一和情况二取最大值
    23.                 dp[i][j] = Math.max(dp[i - 1][j], t + prices[i]);
    24.                 //设置下一轮的t值
    25.                 t = nextT;
    26.                 ans = Math.max(ans, dp[i][j]);
    27.             }
    28.         }
    29.  
    30.         return ans;
    31.     }

            使用动态规划空间压缩技术。

    1.     public static int maxProfit2(int K,int[] prices){
    2.         if (prices ==null|| prices.length==0){
    3.             return 0;
    4.         }
    5.         int N = prices.length;
    6.         if (K>=N/2){
    7.             return allTrans(prices);
    8.         }
    9.         //dp一维表，做了空间压缩
    10.         int[] dp = new int[N];
    11.         int ans = 0;
    12.         for (int tran = 1; tran<=K; tran++){
    13.             int pre = dp[0];
    14.             int best = pre-prices[0];
    15.             for (int index = 1;index
    16.                 pre = dp[index];
    17.                 dp[index] = Math.max(dp[index-1],prices[index]+best);
    18.                 best = Math.max(best,pre-prices[index]);
    19.                 ans = Math.max(dp[index],ans);
    20.             }
    21.         }
    22.         return ans;
    23.     }
    24.  
    25.     public static int allTrans(int[] prices){
    26.         int ans = 0;
    27.         for (int i =0;i
    28.             ans += Math.max(prices[i] - prices[i-1],0);
    29.         }
    30.         return ans;
    31.     }

            测试代码

    1.     public static int[] generateRandomArray(int maxSize, int maxValue) {
    2.         int[] arr = new int[maxSize];
    3.         for (int i = 0; i < arr.length; i++) {
    4.             arr[i] = (int) ((maxValue + 1) * Math.random());
    5.         }
    6.         return arr;
    7.     }
    8.  
    9.     public static void printArray(int[] arr) {
    10.         if (arr == null) {
    11.             return;
    12.         }
    13.         for (int i = 0; i < arr.length; i++) {
    14.             System.out.print(arr[i] + " ");
    15.         }
    16.         System.out.println();
    17.     }
    18.  
    19.     public static void main(String[] args) {
    20.         int maxSize = 20;
    21.         int maxValue = 20;
    22.         int testTime = 100000;
    23.         System.out.println("test begin!");
    24.         for (int i = 0; i < testTime; i++) {
    25.             int[] arr = generateRandomArray(maxSize, maxValue);
    26.             int K = 8;
    27.             int res1 = maxProfit1(K,arr);
    28.             int res2 = maxProfit2(K,arr);
    29.             if (res1!=res2){
    30.                 System.out.println("Oops!");
    31.                 printArray(arr);
    32.                 System.out.println(res1);
    33.                 System.out.println(res2);
    34.                 break;
    35.             }
    36.         }
    37.         System.out.println("test end!");
    38.     }

  • 相关阅读:
    一个 MySQL 隐式转换的坑，差点把服务器整崩溃了
    【微信小程序入门到精通】— 这篇看完直接拿下 text 和 rich-text 组件！
    mysql入门练习
    Spring源码之六-onRefresh()方法
    Java --- JVM之垃圾回收概述
    Nginx 通过userAgent判断是否时搜索引擎蜘蛛
    C++程序设计-第六/七/八章 运算符重载/包含与继承/虚函数和多态性【期末复习|考研复习】
    无监督学习KMeans学习笔记和实例
    Java进阶书籍推荐，赶快收藏起来！
    Vuex的基本使用
  • 原文地址：https://blog.csdn.net/z1171127310/article/details/128066040