演算法入門：最大子序列和的四種演算法（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;
    }
}