01-最大子列和问题（java）

问题描述：给定N个整数的序列{A1，A2，A3，…，An}，求解子列和中最大的值。

这里我们给出{-2，11，-4，13，-5，-2}这样一个序列，正确的最大子列和为20

该题是在数据结构与算法中经常用于分析时间复杂度的典型题目，以下将给出四种方法来求解

方法一：穷举法

 思路：将每一个子列的和都算出来，然后找出最大子列和。

时间复杂度为O(n³)

    public int maxSubSum1(int[] arr) {
        int maxSum = 0;
        //获取数组大小，即循环大小
        int length = arr.length;
        //第一重循序，0 ~ length
        for (int i = 0; i < length; i++) {
            //第二重循序，i ~ length
            for (int j = i; j < length; j++) {
                //每次求和前，将thisSum重置为0
                int thisSum = 0;
                //第三重循序，开始计算子列和
                for (int k = i; k < j; k++) {
                    thisSum += arr[k];
                    //更新最大值
                    if (thisSum > maxSum) {
                        maxSum = thisSum;
                    }
                }
            }
        }
        return maxSum;
    }

 

方法二：穷举法优化

思路：在方法一中，我们需要把每一个子列中的每一项分别相加求和。

我们可以对计算过程进行优化：前一次遍历已经计算出N₁,N₂,..N_i的和sum，那么下一个子列N₁,N₂,..N_i,N_i+1的和即为sum+N_i+1，不需要再把每一项遍历求和了。

时间复杂度为O(n²)

    public int maxSubSum1(int[] arr) {
        int maxSum = 0;
        //获取数组大小，即循环大小
        int length = arr.length;
        //第一重循序，0 ~ length
        for (int i = 0; i < length; i++) {
            //每次求和前，将thisSum重置为0
            //第二重循序，i ~ length，获取子列的同时开始累加
            int thisSum = 0;
            for (int j = i; j < length; j++) {
                thisSum += arr[j];
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

方法三：分而治之思想

思路较复杂，有兴趣的可以百度一下。

方法四：在线处理

一次遍历即求出最大子列和。

时间复杂度为O(n)

思路：将数组从头开始遍历累加，当前和thisSum > maxSum时，那么记录maxSum = thisSum。

　　   当前和thisSum 为负数时，抛弃当前和thisSum（任何负的子序列都不可能是最大子序列的前缀，所以可以知道，只要是首位元素为负数的肯定不是最大子列的组成部分），

将thisSum=0，重新开始累加，直至thisSum > maxSum。

    public  int getMaxSum(int[] arr) {
        int thisSum = 0, maxSum = 0;
        for (int i = 0; i < arr.length; i++) {
            thisSum += arr[i];
            if (thisSum > maxSum) {
                maxSum = thisSum;
            } else {
                thisSum = 0;
            }
        }
        return maxSum;
    }