分治法-最大子段和

发表于： 分类于：
字数： 674 阅读：≈ 2分钟 浏览：

算法思想：分治法

实际问题：最大子段和

编写语言：Java

问题描述

此篇博文是分治法解决最大子段和问题的实现。 问题描述：给定由n个整数(可能为负数)组成的序列A={a1, a2, …, an}，求该序列形如sum(A, i, j)的子段和的最大值。当所有整数均为负整数时，定义其最大子段和为0，依次定义，所求的最大值为：max{0, sum(A, i, j)}， 例如：(a1, a2, a3, a4, a5, a6)=(-2, 11, -4, 13, -5, -2)时，最大子段和为sum(A, 2, 4)=20 算法思想： 1. sum(A, 1, n)==sum(A, 1, n/2) 2. sum(A, 1, n)==sum(A, n/2+1, n) 3. sum(A, 1, n)==sum(A, i, j), 其中 1<=i<=n/2, n/2+1<=j<=n 解释：即序列A的最大子段和可能在A的左半部分，也可能在A的右半部分，还可能跨越了A的左右两个部分

Java代码 

public class MaxSubsequenceSum
{
    public static void main(String[] args)
    {
        int[] a = new int[]{-2, 11, -4, 13, -5, -2};
        int result = maxSubSum(a, 0, a.length - 1);
        System.out.println("maxSubSum(a) = " + result);
    }
    
    /**
      * 使用分治思想求取最大子段和
      * 参数含义：
      *     a: 待求取最大子段和的数组
      *     left：子段起点
      *     right：子段终点
    */
    public static int maxSubSum(int[] a, int left, int right)
    {
        int sum = 0; //sum为总的最大子段和
        if(left == right)
            sum = a[left] > 0 ? a[left] : 0;
        else
        {
            int mid = (left + right) / 2;
            /*
             * 分治求解
            */
            //求左子段的和
            int leftSum = maxSubSum(a, left, mid);
            //求右子段的和
            int rightSum = maxSubSum(a, mid + 1, right);
            //求跨越左右两段的子段和：开始
            int maxLefts = 0;
            int lefts = 0;
            /*
             * 子段是连续的，从中间向两边扩散
             * 若是从左半部分从左边开始计算子段和，可能会导致整体的
             * 左右子段不连续，故左半部分子段和从右边往左边运算，
             * 右半部分子段和从左边往右边运算，保证整体的子段连续
            */
            for(int i = mid; i >= left; i--)
            {
                lefts += a[i];
                if(lefts > maxLefts)
                    maxLefts = lefts;
            }
            int maxRights = 0;
            int rights = 0;
            for(int i = mid + 1; i < right; i++)
            {
                rights += a[i];
                if(rights > maxRights)
                    maxRights = rights;
            }
            sum = maxLefts + maxRights;
            //求跨越左右两段的子段和：结束
            
            //判断得到最大子段和
            if(sum < leftSum)
                sum = leftSum;
            if(sum < rightSum)
                sum = rightSum;
        }
        return sum;
    }
}

运行结果

结果示例