算法入门：最大子序列和的四种算法（Java）

最近再学习算法和数据结构，推荐一本书：Data structures and Algorithm analysis in Java 3rd

以下的四种算法出自本书

四种最大子序列和的算法：

问题描述

给定（可能有负数）整数a(1)、a(2)、……a(n)，求 a(1)+a(2)+……+a(j)的最大值。为方便起见，若所有的整数为负数，则最大子序列和为0.

也就是：在一系列整数中，找出连续的若干个整数，这若干个整数之和 最大。

 

第一种：穷举所有可能，由于嵌套三层for循环，运行时间O(N^3)

package demo1;

public class Demo1 {
    public static void main(String[] args) {
        int[] a = { -2, 4, -3, 5, 7, -1, 8, 1 };
        int max = maxSubSum1(a);
        System.out.println(max);
        // 21
    }

    private static int maxSubSum1(int[] a) {
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                int thisSum = 0;
                for (int k = i; k <= j; k++) {
                    thisSum += a[k];
                }
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }
}

 

第二种：在第一种的基础上简化，撤除一层for循环，运行时间O(N^2)

package demo1;

public class Demo2 {
    public static void main(String[] args) {
        int[] a = { -2, 4, -3, 5, 7, -1, 8, 1 };
        int max = maxSubSum2(a);
        System.out.println(max);
        // 21
    }

    private static int maxSubSum2(int[] a) {
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {
            int thisSum = 0;
            for (int j = i; j < a.length; j++) {
                thisSum += a[j];
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }
}

 

这两种算法本质上类似，后边两种算法将大大提升效率

 

第三种：这里求解的思想完全改变了，时间仅仅O(NlogN)

它把这一组数分成前一半和后一半，再分别针对这两部分处理（分治法）

显而易见：最大子序列和必定是前一段或者后一段或者前后中间这一段这三者之一，再利用递归循环计算

注：代码是越短越好，但是算法未必，这种算法也许很长，但是相比前两种算法它更优秀

代码如下：

package demo1;

public class Demo3 {
    public static void main(String[] args) {
        int[] a = { -2, 4, -3, 5, 7, -1, 8, 1 };
        int max = maxSubSum3(a);
        System.out.println(max);
        // 21
    }

    private static int maxSubSum3(int[] a) {
        // 递归初始化参数
        return maxSumRec(a, 0, a.length - 1);
    }

    private static int maxSumRec(int[] a, int left, int right) {
        // 判断是否只有一个元素
        if (left == right) {
            if (a[left] > 0) {
                return a[left];
            } else {
                return 0;
            }
        }
        int center = (left + right) / 2;
        int maxLeftSum = maxSumRec(a, left, center);
        int maxRightSum = maxSumRec(a, center + 1, right);

        // 左端处理
        int maxLeftBorderSum = 0;
        int leftBoarderSum = 0;
        for (int i = center; i >= left; i--) {
            leftBoarderSum += a[i];
            if (leftBoarderSum > maxLeftBorderSum) {
                maxLeftBorderSum = leftBoarderSum;
            }
        }

        // 右端处理
        int maxRightBoarderSum = 0;
        int rightBoarderSum = 0;
        for (int i = center + 1; i <= right; i++) {
            rightBoarderSum += a[i];
            if (rightBoarderSum > maxRightBoarderSum) {
                maxRightBoarderSum = rightBoarderSum;
            }
        }
        // 返回最大值
        return Math.max(Math.max(maxLeftSum, maxRightSum), maxLeftBorderSum + maxRightBoarderSum);

    }
}

 

第四种方式：最优秀的算法：O(N)

这种方式很巧妙，不易想出，需要有很深编程技术的程序员才能想到

package demo1;

public class Demo4 {
    public static void main(String[] args) {
        int[] a = { -2, 4, -3, 5, 7, -1, 8, 1 };
        int max = maxSubSum4(a);
        System.out.println(max);
        // 21
    }

    private static int maxSubSum4(int[] a) {
        int maxSum = 0;
        int thisSum = 0;
        for (int i = 0; i < a.length; i++) {
            thisSum += a[i];
            if (thisSum > maxSum) {
                maxSum = thisSum;
            } else if (thisSum < 0) {
                thisSum = 0;
            }
            return maxSum;
        }
        return 0;
    }
}