分治策略-股票获取最大收益-最大子数组问题

痛定思痛。 2022-02-16 20:46 253阅读 0赞

分治策略中，递归的求解一个问题，在每层递归中有如下三个步骤：  
分解：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小  
解决：递归地求解出子问题，如果子问题的规模足够小，则停止递归，直接求解  
合并：将子问题的解组合成原问题的解

递归式  
三种求解递归式的方法：  
代入法：猜测一个界，然后用数学归纳法证明这个界是正确的  
递归树法：将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式  
主方法：可求解形如下面公式的递归式的界：(常使用的方法)  
T（n） = aT(n/b) + f(n)

股票收益最大：  
你被准许可以在某个时刻买进一股该公司的股票，并在之后某个日期将其卖出，买进卖出都是在当天交易结束后进行，你的目标是最大化收益。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
图中表明，有时最大收益既不是最低价格时买进，也不是在最高价格时卖出。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
解决方法：

1.  暴力法：  
    简单尝试每对可能的买进和卖出的日期组合，只要卖出日期在买入日期之后即可n天中这种方法运行时间时O（n^2）.
2.  问题变换（最大子数组）  
    我们的目的时寻找一段日期，使得从第一天到最后一天的股票价格变化定义为第i天和第i-1天的价格差。  
    问题就转换为：寻找A 的和最大的非空连续子数组，称这样的连续子数组为最大子数组。  
    ![在这里插入图片描述][20190419093251859.png]  
    对于图中数组，A\[1…16\]的最大子数组为A\[8…11\].和为43

寻找最大子数组问题的更高效的求解方法  
使用分治策略的求解方法

package 算法导论;
    /*
    股票获取最大收益
     */
    public class 分治策略最大子数组 {
        public static void main(String[] args) {
        
        //        int[] priceChange = new int[price.length -1 ];
    //        for(int i = 1;i<price.length;i++){
    //            priceChange[i-1] = price[i] - price[i-1];
    //        }
            int[] priceChange = new int[]{13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
            //int[] priceChange = new int[price.length -1 ];
            baoli(priceChange);
            int[] max = findMaximumSubarray(priceChange,0,priceChange.length-1);
            for(int i = max[0]; i <= max[1]; i++) {
                // 打印每个元素
                System.out.print(priceChange[i] + ", ");
            }
            System.out.println("和为："+ max[2]);
        }
      /*
        方法1：暴力求解：遍历每一个子数组区间，比较大小，并记录最大收益的开始和结束的下标
         */
        public static void baoli(int[] priceChange) {
    
            int sum = priceChange[0];
            int startIndex = 0;
            int endIndex = 0;
    
            for (int i = 0; i < priceChange.length; i++) {
                int tempSum = 0;
                for (int j = i; j < priceChange.length; j++) {
                    tempSum += priceChange[j];
                    if (tempSum > sum) {
                        startIndex = i;
                        endIndex = j;
                        sum = tempSum;
                    }
                }
                System.out.println("收益为" + tempSum);
            }
            System.out.println("最大收益为" + sum);
        }
    
        /*
        分治法
    
    解题思路：将数组分成两份，最大子数组（元素之和最大）只有三种情况：
    （1）最大子数组在mid左边，即：startIndex和endIndex都在mid左边
    （2）最大子数组一半在左边，一半在右边，即：startIndex在 mid左边，endIndex在mid右边
    （3）最大子数组在mid右边，即：startIndex和endIndex都在mid右边
    那么比较三种情况下的最大子数组的结果接可以了，最终得出最大子数组
    那么继续运用递归，继续给mid左边和右边进行分治求解，将复杂的问题进行简化，以此降低了代码的时间复杂度，提高了程序的运行效率。
         */
       /*
       求出该数组索引在low到high中的元素的最大子数组
       子数组必须跨越索引为mid的元素，即包含索引为mid的元素
        */
       public static int[] findMaxCrossingSubarray(int[] arr,int low ,int mid,int high){
           //左边数组最大数组的和，0x80000000是int所能表示的最小值
           int leftSum = 0x80000000;
           //左边数组累加的和
           int sum = 0;
           int maxLeft = mid;
           //遍历数组
           for(int i = mid;i>=low;i--){
               sum += arr[i];
               //如果累加的和大于最大子数组的和，则替换最大子数组
               if(sum > leftSum){
                   //最大子数组左边的索引
                   maxLeft = i;
                   //替换左边最大子数组的和
                   leftSum = sum;
               }
           }
           //右边数组最大子数组的和，0x80000000是int 所能表示的最小值
           int rightSum = 0x80000000;
           //右边数组累加的和
           sum = 0;
           int maxRight = mid+1;
           for(int i = mid +1;i<=high;i++){
               sum += arr[i];
               //如果累加的和大于最大子数组的和，则替换最大子数组
               if(sum > rightSum){
                   //最大子数组右边的索引
                   maxRight = i;
                   //替换右边最大子数组的和
                   rightSum = sum;
               }
           }
           return  new int[] {maxLeft,maxRight,leftSum+rightSum};
       }
       /*
       求出该数组索引在Low到high中的元素的最大子数组
        */
       public static int[] findMaximumSubarray(int[] arr,int low,int high){
           //此时只有一个元素，最大子元素就是它本身
           if(low == high) return new int[] {low,high,arr[low]};
    
           //中间数
           int mid = (low+high)/2;
           //求得左边数组的最大子数组
           int[] leftMax = findMaximumSubarray(arr,low,mid);
           //求得右边数组的最大子数组
           int[] rightMax = findMaximumSubarray(arr,mid+1,high);
           //求得跨越中点的最大子数组
           int[] crossMax = findMaxCrossingSubarray(arr,low,mid,high);
    
           //比较这三个子数组的和的大小
           //左边子数组大
           if(leftMax[2]>=rightMax[2] && leftMax[2]>=crossMax[2])return leftMax;
           //右边子数组大
           else if(rightMax[2]>=leftMax[2] && rightMax[2] >= crossMax[2]) return rightMax;
           //跨越中点的子数组最大
           else return crossMax;
       }
    }

参考：  
1.[https://blog.csdn.net/qq\_43158436/article/details/84875953][https_blog.csdn.net_qq_43158436_article_details_84875953]  
2.[https://blog.csdn.net/qq\_34937637/article/details/81282952][https_blog.csdn.net_qq_34937637_article_details_81282952]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220217/00c443d10881450d868e5ea8fba4a5d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220217/9c962863171f48e7adda37e8c1b2018a.png
[20190419093251859.png]: /images/20220217/d7dfbd5298c34b77a507518fc65662c2.png
[https_blog.csdn.net_qq_43158436_article_details_84875953]: https://blog.csdn.net/qq_43158436/article/details/84875953
[https_blog.csdn.net_qq_34937637_article_details_81282952]: https://blog.csdn.net/qq_34937637/article/details/81282952