最大子列和

给定 K 个整数组成的序列 {$N_1, N_2, ..., N_K$}，“连续子列”被定义为 {$N_i, N_i+1, ... N_j$}，其中 1 <= i <= j <= K. “最大子列和”被定义为所有连续子列元素中最大者。例如给定序列 {-2, 11, -4, 13, -5, -2}，其连续子列 {11, -4, 13} 有最大的和 20. 求程序以计算最大子列和。

数据特点

数据1：与样例等价，测试基本正确性；
数据2：$10^2$ 个随机整数；
数据3：$10^3$ 个随机整数；
数据4：$10^4$ 个随机整数；
数据5：$10^5$ 个随机整数；

输入

第一行给出正整数 K ($K <= 100,000$)；
第二行给出 K 个整数，中间以空格分隔。

输出

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出 0.

输入输出样例

Input

6
-2 11 -4 13 -5 -2

Output

20

解法分析

暴力穷举

算法利用三层循环分别确定子列左端点、右端点和子列内的遍历。
每次更新子列时便重新计算当前列的和，遍历累加判断是否需要更新最大和。

时间复杂度： $O(n^3)$.

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = in.nextInt();
    }

    int maxSum = 0;
    int currentSum = 0;

    // 暴力穷举法 （类似 nested loop join）
    for(int i = 0; i < n; i++) {    // i 为子列左端
        for(int j = i; j < n; j++) {    // j 为子列右端
            currentSum = 0; // currentSum 为当前子列和，每次更新子列时清零
            for(int k = i; k <= j; k++) {    // k 为累加指针，从 i 到 j 逐个累加
                currentSum += arr[k];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
    }
    System.out.println(maxSum);
}

分部累加

算法利用两层循环分别确定子列左端和右端，在遍历时便进行累加判断操作。
对于每个相同的左端，每次更新一个右端。利用上一次的和来判断当前状态是否需要更新最大和。

时间复杂度： $O(n^2)$.

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = in.nextInt();
    }

    int maxSum = 0;
    int currentSum = 0;

    // 分部穷举法 （类似 page oriented loop join）
        for (int i = 0; i < n; i++) {
            currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += arr[j];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        System.out.println(maxSum);
}

递归分治

算法利用递归思想，把问题分解成三块：中线平分后左子列最大和；中线平分后右子列最大和；跨越中线的最大和。比较三个数值得出最终结果。
对于跨越中线的子列和计算方法为：

• 1）从中线向左遍历累加，直到遇到会让子列和下降的元素前停止。
• 2）从中线向右遍历累加，直到遇到会让子列和下降的元素前停止。
• 3）将上述结果相加得出最终结果。

时间复杂度：
记时间复杂度为 $T(N)$.
则有:
$$T(N)=T(\frac{N}{2})+ T(\frac{N}{2})+cN \quad (1)$$ （即左子列复杂度 + 右子列复杂度 + 跨中线子列复杂度）

将 $T(\frac{N}{2})$ 展开有： $$T(\frac{N}{2})=T(\frac{N}{4})+ T(\frac{N}{4})+c\frac{N}{2} \quad (2)$$
将 $(2)$ 带入 $(1)$ 有：
$$T(N)=2(2T(\frac{N}{4})+c\frac{N}{2})+cN$$
$$T(N)=2^2T(\frac{N}{2^2})+2cN$$
继续展开到 k 阶有：
$$T(N)=2^kT(\frac{N}{2^k})+kcN$$
展开 k 步后，函数 T 的自变量变为 1，即： $T(\frac{N}{2^k}) = T(1) = O(1)$，
（即当递推到终止条件时，元素只有一个）

此时可认为：$\frac{N}{2^k} = 1$, 即 $N=2^k$, $k=logN$.

则有：
$$T(N)=2^kT(1)+kcN$$
则：
$$T(N)=O(N)O(1)+O(NlogN) = O(NlogN)$$

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = in.nextInt();
    }

    // 递归分治法
    System.out.println(divideAndConquer(arr, 0, n - 1));
}

// 分治法求从 arr[left] 到 arr[right] 的最大子列和
public static int divideAndConquer(int[] arr, int left, int right) {
    // 左右子问题结果
    int maxLeftSum;
    int maxRightSum;

    // 跨界问题结果
    int maxLeftBorderSum;
    int maxRightBorderSum;

    // 变量
    int leftBorderSum;
    int rightBorderSum;
    int center;

    // 子列只有一个元素；递归的终止条件
    if (left == right) {
        if(arr[left] > 0) {
            return arr[left];
        } else {
            return 0;
        }
    }

    // 拆分数组
    center = (left + right) >> 1;

    // 递归求解
    maxLeftSum = divideAndConquer(arr, left, center);
    maxRightSum = divideAndConquer(arr, center + 1, right);

    // 求跨界结果
    maxLeftBorderSum = 0;
    leftBorderSum = 0;
    for (int i = center; i >= left; i--) {    // 从中线向左扫描
        leftBorderSum += arr[i];
        if (leftBorderSum > maxLeftBorderSum) {
            maxLeftBorderSum = leftBorderSum;
        }
    }

    maxRightBorderSum = 0;
    rightBorderSum = 0;
    for (int i = center + 1; i <= right; i++) {    // 从中线向右扫描
        rightBorderSum += arr[i];
        if (rightBorderSum > maxRightBorderSum) {
            maxRightBorderSum = rightBorderSum;
        }
    }

    // 比较返回结果
    return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

public static int max3(int a, int b, int c) {
    return a > b ? (a > c ? a : c) : (b > c ? b : c);
}

在线处理

算法遍历全部输入，期间计算当前子列和并判断是否更新最终结果。
每读入一个数字，累加到上一次的结果上，进行比较是否需要更细结果；
但若当前子列和为负，则证明当前子列不可能使得下一个元素加入后的子列更大，则重新计数。

时间复杂度：$O(n)$.

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = in.nextInt();
    }

    int maxSum = 0;
    int currentSum = 0;

    // 在线处理法
    for (int i = 0; i < n; i++) {
        currentSum += arr[i];    // 向右累加
        if (currentSum > maxSum) {
            maxSum = currentSum;    // 当发现累加使得结果更大，更新结果
        } else if (currentSum < 0) {    // 当发现当前和为负，则无法使得后续新增元素子列和更大，清零
            currentSum = 0;
        }
    }
    System.out.println(maxSum);
}