# 最大子列和

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

# 数据特点

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

# 输入

第一行给出正整数 K ()；
第二行给出 K 个整数，中间以空格分隔。

# 输出

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

# 输入输出样例

Input

6
-2 11 -4 13 -5 -2

1
2

Output

# 解法分析

# 暴力穷举

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

时间复杂度： .

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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 分部累加

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

时间复杂度： .

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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 递归分治

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

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

时间复杂度：
记时间复杂度为 .
则有:

（即左子列复杂度 + 右子列复杂度 + 跨中线子列复杂度）

将展开有：

将

带入

有：

继续展开到 k 阶有：

展开 k 步后，函数 T 的自变量变为 1，即：

，
（即当递推到终止条件时，元素只有一个）

此时可认为：, 即 , .

则有：

则：

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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

# 在线处理

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

时间复杂度：.

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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

← 算法数组、链表、栈和队列相关的题目 →