算法-最大子数组

概要

在给定的一个数组中，求解收益最大化。只可以操作一次。
只可操作一次，就需要确保数组是连续的。

整体架构流程

使用分治策略的求解法：
假定我们寻找子数组A[low,high]的最大子数组。使用分治技术意味着我们需要将子数组划分为两个规模尽量相等的子数组。找到子数组的中央位置mid=(low+high)/2。然后求解两个子数组A[low,mid]和A[mid+1,high]。A[low,high]的任何连续子数组A[i,j]所处位置必然是以下三中情况之一：

1. 完全位于左子数组A[low,mid]中，因此low<=i<=j<=mid。
2. 完全位于右子数组A[mid+1,high]中，因此mid+1<=i<=j<=hight。
3. 跨越中间点，因此low<=i<=j<=hight。

技术细节

public class MaxSubArray {

    static class MaxVo {
         //最小索引值
        public int lowIndex;
        //最大索引值
        public int highIndex;
        //在low至high的最大值
        public int maxSum;
        public MaxVo(int lowIndex, int highIndex, int maxSum){
            this.lowIndex = lowIndex;
            this.highIndex = highIndex;
            this.maxSum = maxSum;
        }

        @Override
        public String toString() {
            return "MaxVo{" +
                    "lowIndex=" + lowIndex +
                    ", highIndex=" + highIndex +
                    ", maxSum=" + maxSum +
                    '}';
        }
    }
    public static void main(String... args){
        int[] arr = {13,3,9,-5,1};
        MaxVo maxVo = findMaxSubArray(arr,0, arr.length-1);
        System.out.println(maxVo.toString());
    }

    /**
     * 递归
     * @param arr 数组
     * @param low 下标
     * @param high 上标
     * @return 最大子数组
     */
    private static MaxVo findMaxSubArray(int[] arr, int low, int high){
        if(low == high){
            //最小递归的数据
            return new MaxVo(low,high,arr[low]);
        }else {
            int mid = (low + high)/2;
            //左边的最大子数组
            MaxVo lowVo = findMaxSubArray(arr,low,mid);
            //右边的最大子数组
            MaxVo highVo = findMaxSubArray(arr,mid+1, high);
            //左右合并的最大子数组
            MaxVo crossVo = findMaxCrossingSubArray(arr,low,mid,high);
            //返回low至high的最大子数组
            if(lowVo.maxSum >= highVo.maxSum && lowVo.maxSum >= crossVo.maxSum){
                return lowVo;
            } else if (highVo.maxSum >= lowVo.maxSum && highVo.maxSum >= crossVo.maxSum) {
                return highVo;
            }else {
                return crossVo;
            }
        }
    }

    /**
     * 发现合并的两个，最大子数组
     * @param arr 数组
     * @param low 最小索引
     * @param mid 中间索引
     * @param high 最大索引
     * @return low至high的最大子数组
     */
    private static MaxVo findMaxCrossingSubArray(int[] arr, int low, int mid, int high){
        int lowSum = 0;
        int lowIndex = mid;
        int sum = 0;
        //获取左边最大子数组
        //获取左边数组累计最大值，和最小的索引位置
        for(int i = mid; i >= low; i--){
            sum+= arr[i];
            if(sum > lowSum){
                lowSum = sum;
                lowIndex = i;
            }
        }
        int highSum = 0;
        int highIndex = mid + 1;
        sum = 0;
        //获取右边最大子数组
        //获取右边数组累计最大值，和最小的索引位置
        for(int i = mid+1; i <= high; i++){
            sum += arr[i];
            if(sum > highSum){
                highSum = sum;
                highIndex = i;
            }
        }
        return new MaxVo(lowIndex,highIndex,lowSum+highSum);
    }
}

小结

求解到的是一个最大的子数组，而不是最大子数组，因最大子数组有可能有多个。