最大子序列，也可以理解为最大子序列和问题，做LeetCode的第121题的时候用到了这个内容，看了看Discuss发现解法非常简单，但是道理却不简单，正好数据结构与算法分析中也有这部分的内容，正好整理出来，也是自己理清思路。
具体每一个算法的思路都通过注释的形式放到了代码里，也方便理解。

问题：给定数组array，求这个数组的最大子序列。

最容易想到的方法 穷举法

时间复杂度O(N^3)

/**
 * @author ahscuml
 * @date 2018/8/14
 * @time 21:35
 */
public class BruteForce {
    public static int MaxSubArray(int[] array) {
        // 子序列最大值
        int max = array[0];
        // 最大子序列的左右下标
        int left = 0,right = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j <= i; j++) {
                // 这是这次循环的值,默认为0
                int cyclemax = 0;
                for (int k = j; k <= i; k++) {
                    cyclemax += array[k];
                }
                // 保存最大子序列的左右下标
                if (cyclemax > max) {
                    left = j;
                    right = i;
                    max = cyclemax;
                }
            }
        }
        // 输出最大子序列
        for (int i = left; i <=right ; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
        return max;
    }
}

穷举法的改进

时间复杂度O(N^2)

/**
 * @author ahscuml
 * @date 2018/8/14
 * @time 22:16
 */
public class BruteForceOpt {
    public static int MaxSubArray(int[] array) {
        // 子序列最大值
        int max = array[0];
        // 最大子序列的左右下标
        int left = 0, right = 0;
        for (int i = 0; i < array.length; i++) {
            // 这是这次循环的值,默认为0
            int cyclemax = 0;
            for (int j = i; j >= 0; j--) {
                // 替换了内部的一个循环，减少了不必要的计算，降低复杂度
                cyclemax += array[j];
                // 保存最大子序列的左右下标
                if (cyclemax > max) {
                    left = j;
                    right = i;
                    max = cyclemax;
                }
            }
        }
        // 输出最大子序列
        for (int i = left; i <= right; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
        return max;
    }
}

递归算法

时间复杂度O(NlogN)

/**
 * @author ahscuml
 * @date 2018/8/14
 * @time 22:22
 */
public class Recursion {
    private static int maxSubArrayRec(int[] array, int left, int right) {
        // 递归最基本的情况，如果只有一个数字，不用递归。
        if (left == right) {
            if (array[left] > 0) {
                return array[left];
            } else {
                return 0;
            }
        }
        // 递归的两种情况，左边最大和右边最大
        int center = (left + right) / 2;
        int maxLeftSum = maxSubArrayRec(array, left, center);
        int maxRightSum = maxSubArrayRec(array, center + 1, right);
        // 递归的第三种情况，中间最大，但是中间最大需要计算左边加上边界最大和右边加上边界最大
        int maxLeftBorderSum = 0, leftBorderSum = 0;
        for (int i = center; i >= left; i--) {
            leftBorderSum += array[i];
            if (leftBorderSum > maxLeftBorderSum) {
                maxLeftBorderSum = leftBorderSum;
            }
        }

        int maxRightBorderSum = 0, rightBorderSum = 0;
        for (int i = center + 1; i <= right; i++) {
            rightBorderSum += array[i];
            if (rightBorderSum > maxRightBorderSum) {
                maxRightBorderSum = rightBorderSum;
            }
        }
        // 返回三种情况的最大值
        return Math.max(maxLeftBorderSum, Math.max(maxRightSum, maxLeftBorderSum + maxRightBorderSum));
    }

    public static int maxSubArray(int[] array) {
        return maxSubArrayRec(array, 0, array.length - 1);
    }
}

Kadane算法

时间复杂度O(N)，动态规划算法。
Kadane的算法以一个简单的归纳问题开始：如果我们知道在位置i结束的最大子阵列和，那么在位置 i + 1 处结束的最大子阵列总和是多少？ 答案结果相对简单：在位置 i + 1 结束的最大子阵列和包括在位置i结束的最大子阵列和作为前缀，或者它不包括。 因此，我们可以通过在数组上迭代一次来计算在所有位置i的位置i处结束的最大子阵列和。 当我们走的时候，我们只是跟踪我们所见过的最大数值。

/**
 * @author ahscuml
 * @date 2018/8/14
 * @time 22:51
 */
public class Easy {
    public static int maxSubArrary(int[] array) {
        // maxSum是最大子序列的和，thisSum是以当前为终点的最大子序列的和
        int maxSum = array[0], thisSum = 0;
        // leftpre是以当前为终点的最大子序列的和的左下标，left是最大子序列和的下标，right是最大子序列和的右下标
        int leftpre = 0, left = 0, right = 0;
        for (int i = 0; i < array.length; i++) {
            thisSum += array[i];
            if (thisSum > maxSum) {
                maxSum = thisSum;
                right = i;
                left = leftpre;
            } else if (thisSum < 0) {
                thisSum = 0;
                if (i != array.length - 1) {
                    leftpre = i + 1;
                }
            }
        }
        // 输出最大子序列
        for (int i = left; i <= right; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
        return maxSum;
    }
}

This blog is under a CC BY-NC-SA 4.0 Unported License
本文链接：https://ahscuml.github.io/最大子序列/