给定N个整数序列{A1,A2,...,An}...，通过三种解法

前言

以下根据浙江大学数据结构慕课第八至十课“算法实例”所做笔记并编写相应Java程序。

给定N个整数的序列{A₁,A₂,...,A_n}，求函数f(i,j)=max( 0,\sum_{k=i}^j A_k )的最大值.

解：分析题目，是求一个函数 f 的最大值，此函数是求一个序列中A_i到A_j连续的子列的和。
例：以序列{4,-3,5,-2,-1,2,6,-2}为例

算法一：求出所有连续子列和，然后比较找出其中最大的值

主要代码如下

/**
* Created by IntelliJ IDEA.
* User: Greyson
* Date: 8/9/2018
* Time: 1:00 PM
*/
public class MaxSubseqSum1 {
   public static void main(String[] args) {
       maxSubseqSum(new int[]{4,-3,5,-2,-1,2,6,-2});
   }
   private static void maxSubseqSum(int[] array) {
       int thisSum,maxSum = 0;                // thisSum是A<sub>i</sub>到A<sub>j</sub>的子列和，maxSum用于保存thisSum中较大的值
       for (int i = 0; i < array.length; i++) {  // i是子列左端位置
           for (int j = i; j < array.length; j++) {  // j是子列右端位置
               thisSum = 0;                            
               for (int k = i; k <= j; k++) {
                   thisSum += array[k];
                   if (thisSum > maxSum) {     // 如果得到的子列和要更大
                       maxSum =thisSum;        // 则更新maxSum中的值
                   }
               }
           }
       }
       System.out.println(maxSum);
   }
}

其结果如下: image.png

此算法嵌套了三层循环，其复杂度：T(N)=O(N^3)。

算法二：

/**
 * Created by IntelliJ IDEA.
 * User: Greyson
 * Date: 8/9/2018
 * Time: 1:56 PM
 */
public class MaxSubseqSum2 {
    public static void main(String[] args) {
        System.out.println(maxSubseqSum(new int[]{4,-3,5,-2,-1,2,6,-2}));
    }
    private static int maxSubseqSum(int[] array) {
        int thisSum,maxSum = 0;                    // thisSum是A<sub>i</sub>到A<sub>j</sub>的子列和，maxSum用于保存thisSum中较大的值
        for (int i = 0; i < array.length; i++) {        // i是子列左端位置
            thisSum = 0;
            for (int j = i; j < array.length; j++) {      // j是子列右端位置
                thisSum += array[j];
                if (thisSum > maxSum) {          // 如果得到的子列和要更大
                        maxSum = thisSum;        // 则更新maxSum中的值
                }
            }
        }
        return maxSum;
    }
}

此算法只嵌套了两层循环，其复杂度：T(N)=O(N^2)。

算法三：分而治之

设计思想：将一个难以解决的问题分割成各个小问题，待各个击破再合并解决。
分析序列{4,-3,5,-2,-1,2,6,-2}

image.png
如图，将八个数不断从中间断开，直至两个数为一层，从最底层起开始分析，也就是第二层。
注意：该函数所查找的是序列中连续的子序列和的最大值，注意“连续的”这三个字。

1. 两个数中寻找最大值，皆是其正数即：4，5，2，6
2. 从跨越中间开始找，左边部分最大值是6（注意不是9，因为是连续的，如果5+4那么必然要加上-3）
3. 右边同理其最大值也是跨越中间的部分为8
4. 此时可以算出该函数的最后结果值：（8+6）+ {（-2）+（-1）} = 11。

根据该算法我们可以知道最大连续子列和要么在左边，要么右边，要么跨越两边，所以分别列出三种情况并比较，其中最大值就是该题的解。

由于水平见拙，尝试了很久没有复现，代码部分略，以后再补充。

算法四：在线处理

public class MaxSubseqSum3 {
    public static void main(String[] args) {
        System.out.println(maxSubseqSum(new int[]{4,-3,5,-2,-1,2,6,-2}));
    }
    private static int maxSubseqSum(int[] array) {
        int thisSum = 0, maxSum = 0;
        for (int i = 0; i < array.length; i++) {
            thisSum += array[i];
            if (thisSum > maxSum) {
                maxSum = thisSum;
            } else if (thisSum < 0) {
                thisSum = 0;
            }
        }
        return maxSum;
    }
}

该算法的复杂度为T(N)=O(N)，也是此题的最优解。