问题：

• 给定由n个整数组成的序列a1，a2，a3…，an，求该序列子段的最大和。即一段连续子序列的最大和：
  $$max\{0,\underset{0\le i\le j<n}{\max }\sum _{k=i}^j{a}_k\}$$

简单算法——暴力求解

//  MaxSum.java
/**
 * @author DWJ
 * 枚举所有的可能的序列，找出和最大的那一个
 */
public class MaxSum {
    private static int left, right;  // 用于保存子序列的左右边界
    
    public static void main(String[] args) {
        int[] array = {1, 2, 3, -2, 4, 7, -5, -6, 9, 6};
        int max = maxSum(array.length, array);
        System.out.println("最大子序列和："+ left +" to "+ (right-1)+": "+ max);
    }
    
    private static int maxSum(int n, int[] array){
        int sum = 0;
        for (int i = 0; i < n; i++) {   // 序列左边界
            for (int j = i; j < n; j++) {    //序列右边界
                int thisSum = 0;
                for (int k = i; k <= j; k++)     // 子序列求和i
                    thisSum += array[k];

                if (thisSum > sum) {  // 更新结果
                    sum = thisSum;
                    left = i;
                    right = j;
                }
            }
        }
        return sum;
    }
}

• 算法复杂度 $O(n^3)$

简单算法——暴力求解改进

    /**
     * 改进： 将确定子序列与子序列求和结合起来
     *
     * @param n     序列长度
     * @param array 待解序列
     * @return 最大子序列
     */
    private static int maxSum2(int n, int[] array) {
        int sum = 0;
        for (int i = 0; i < n; i++) {  // 子序列的左边界
            int thisSum = 0;
            for (int j = i; j < n; j++) {   // 子序列的有边界
                thisSum += array[j];       // 子序列之和

                if (thisSum > sum) {    // 更新结果
                    sum = thisSum;
                    left = i;
                    right = j;
                }
            }
        }
        return sum;
    }

• 算法复杂度$O(n^2)$

分治算法求解

• 如果将所给的序列 $a[1:n]$分为长度相等的两端$a[1:n/2]$和$a[n/2+1:n]$，分别求出这两段的最大子段和，则 $a[1:n]$的最大子段和有三种情形：
  ① $a[1:n]$的最大字段和与$a[1:n/2]$的最大字段和相同
  ② $a[1:n]$的最大字段和与$a[n/2+1:n]$的最大字段和相同
  ③ $a[1:n]$的最大字段和为：$sum(a_i:a_j)$ (且 $1<=i<=n/2,n/2+1<=j<=n$)
  • ①和② 可递归求
  • 对于情形③，可知，$a[n/2]$和$a[n/2+1]$这两个元素在最优子序列中。
• 算法如下：

/**
 * @author DWJ
 * 求最大子序列和的 分治算法
 */
public class MaxSubSum {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, -2, 4, 7, -5, -6, 9, 6};  // 定义待测数组
        System.out.println(maxSum(a.length, a));     // 输出结果
    }

    /**
     * 
     * @param n 数组长度
     * @param array 待测数组
     * @return 最大子序列和
     */
    private static int maxSum(int n, int[] array) {
        return maxSubSum(array, 0, n - 1);
    }

    private static int maxSubSum(int[] subArray, int left, int right) {
        int sum;
        if (left == right)
            sum = Math.max(subArray[left], 0);
        else {
            int center = (left + right) / 2;    // 中点
            int leftSum = maxSubSum(subArray, left, center);      // 左边最大子序列和
            int rightSum = maxSubSum(subArray, center + 1, right);     // 右边最大子序列和

            // 下面计算跨中点的最大子序列和

            int s1 = 0;        // 左边包含subArray[center] 的最大序列和
            int lefts = 0;     // 中间值
            for (int i = center; i >= left; i--) {
                lefts += subArray[i];
                if (lefts > s1)
                    s1 = lefts;
            }

            int s2 = 0;       // 右边包含subArray[center+1] 的最大序列和
            int rights = 0;   //中间值
            for (int i = center + 1; i <= right; i++) {
                rights += subArray[i];
                if (rights > s2)
                    s2 = rights;
            }

            sum = s1 + s2;    // s1 + s2 为跨中点的最大序列和

            // 选出 三个值 中最大的值
            if (sum < leftSum)
                sum = leftSum;
            if (sum < rightSum)
                sum = rightSum;
        }
        return sum;    // 返回最大值
    }
}

• 分治算法递归式：
  $$T(n)=\{\begin{array}{ll}O(1),& \text{n ≤ c}\\ 2T(n/2)+O(n),& \text{n > c}\end{array}$$
• 算法的复杂度：$O(nlogn)$

动态规划算法求解

• 先分析下列问题：
  $$若定义b：b[j]=\underset{0\le i\le j}{\max }\{\sum _{k=i}^{j}a[k]\}$$
• 则可知，当$b[j-1]>0$时， $b[j]=b[j-1]+a[j]$; 否则$b[j]=a[j]$.由此可得动态规划递归式：
  $$b[j]=max\{b[j-1]+a[j],a[j]\}$$
• 代码如下：

/**
 * @author DWJ
 * 最大子序列和的 动态规划 算法
 */
public class MaxSubSum_3 {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, -2, 4, 7, -5, -6, 9, 6};  // 定义待测数组
        System.out.println(maxSum(a.length, a));     // 输出结果
    }

    /**
     * @param n 数组的长度
     * @param array 待测数组
     * @return 最大子序列和
     */
    private static int maxSum(int n, int[] array) {
        int sum = 0, b = 0;  // 定义中间值b

        for (int i = 0; i < n; i++) {
            if (b > 0)       // 实现上述的动态规划递归式
                b += array[i];
            else
                b = array[i];
            
            if (b > sum)   // 更新结果
                sum = b;
        }
        return sum; // 返回结果
    }
}

• 算法复杂度：$O(n)$