7-1最大子列和问题

题目描述

题目地址为:https://pintia.cn/problem-sets/15/problems/709

给定\({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}\)个随机整数；

输入格式:

输入第1行给出正整数\(K (≤100000)\)；第2行给出\(K\)个整数，其间以空格分隔。

输出格式:

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

输入样例:

1
2
6
-2 11 -4 13 -5 -2

输出样例:

1
20

法一 动态规划

思考

考虑整个n长度的数组，序号是从0到n-1的。对于任意的子序列都肯定会有一个结尾的序号。这样就可以想象一个数组，记录的值就是以当前序号为结尾的子序列的最大子列和。

已知前一个的值，怎么求后面的值？就是考虑之后的那个数组值加到之前的序列是比本身大还是小。如果小就把之前的值舍弃，否则就加入。

那么动态规划转移方程就是:

\[ f(i) = max \{ f(i-1) + nums[i] , nums[i] \} \]

然后考虑全为负数的情况。很容易就想到，当序列中只要存在一个正数那么最大子列和都应该大于0而不是小于0，所以当最大子列和为负时所有值为复数。

那如果只存在0和负数呢？同理可得，最大子列和为0。也就不在考虑范围内。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int maxSubArray(int* nums, int numsSize){
    int pre = 0, maxAns = nums[0];
    for (int i = 0; i < numsSize; i++) {
        pre = fmax(pre + nums[i], nums[i]);
        maxAns = fmax(maxAns, pre);
    }
    return maxAns < 0 ? 0 : maxAns;
}

int main() {
    int numsSize;
    scanf("%d", &numsSize);
    int* nums = (int*)malloc(sizeof(int) * numsSize); 
    for(int i = 0 ; i < numsSize ; i++) {
        scanf("%d",&nums[i]);
    }
    printf("%d",maxSubArray(nums,numsSize));
    return 0;
}

法二 分治

思考

(以下想法来自LeetCode)

先试想定义一个操作get(a, l ,r)表示查询a序列\([l,r]\)区间内的最大子段和。那么这道题就是求get(nums, 0 , nums.size() - 1)。

如何分治实现这个操作呢？对于一个区间\([l,r]\)，我们取\({\lfloor m = \frac {l+r} {2} \rfloor }\)，对区间\({[l,m]}\)和\([m+1,r]\)分治求解。当递归逐层深入知道区间长度为1的时候，递归开始回升。

这个时候我们考虑如何通过 \([l,m]\) 区间的信息和 \([m+1,r]\) 区间的信息合并成区间 \([l,r]\) 的信息。最关键的两个问题是：

  • 我们要维护区间的哪些信息呢？
  • 我们如何合并这些信息呢？

对于一个区间 \([l,r]\)，我们可以维护四个量：

  • \({lSum}\) 表示 \([l,r]\) 内以 \({l}\) 为左端点的最大子列和
  • \({rSum}\) 表示 \([l,r]\) 内以 \({r}\) 为右端点的最大子列和
  • \({mSum}\) 表示 \([l,r]\) 内的最大子列和
  • \({iSum}\) 表示 \([l,r]\) 的区间和

对于长度为1的区间，四个值的量都与\({nums[i]}\)相等

对于长度大于1的区间：

  • 首先最好维护的就是\({iSum}\)，区间\({[l,r]}\)的\({iSum}\)就等于左子区间的\({iSum}\)加上右子区间的\({iSum}\)。

  • 对于\({[l,r]}\)的\({lSum}\)，存在两种情况，它要么等于左子区间的\({lSum}\)，要么等于左子区间的\({iSum}\)加上右区间的\({lSum}\)，二者取大。

  • 对于\({[l,r]}\)的\({rSum}\)，同理，它要么等于右子区间的\({rSum}\)，要么等于右子区间的\({iSum}\)加上左子区间的\({rSum}\)，二者取大。

  • 当计算好上面的三个量之后，就很好计算\({[l,r]}\)的\({mSum}\)了。我们可以考虑\({[l,r]}\)的\({mSum}\)对应的区间是否跨越m——它可能不跨越m，也就是说\({[l,r]}\)的\({mSum}\)可能是左子区间的\({mSum}\)和右子区间的\({mSum}\)中的一个；它也可能跨越m，可能是左子区间的\({rSum}\)和右子区间的\({lSum}\)求和。三者取大。

具体代码

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Status {
    int lSum, rSum, mSum, iSum;
};

struct Status pushUp(struct Status l, struct Status r) {
    int iSum = l.iSum + r.iSum;
    int lSum = fmax(l.lSum, l.iSum + r.lSum);
    int rSum = fmax(r.rSum, r.iSum + l.rSum);
    int mSum = fmax(fmax(l.mSum, r.mSum), l.rSum + r.lSum);
    return (struct Status){lSum, rSum, mSum, iSum};
};

struct Status get(int* a, int l, int r) {
    if (l == r) {
        return (struct Status){a[l], a[l], a[l], a[l]};
    }
    int m = (l + r) >> 1;
    struct Status lSub = get(a, l, m);
    struct Status rSub = get(a, m + 1, r);
    return pushUp(lSub, rSub);
}

int maxSubArray(int* nums, int numsSize) {
    int max = get(nums, 0, numsSize - 1).mSum;
    return max < 0 ? 0 : max;
}

int main() {
    int numsSize;
    scanf("%d", &numsSize);
    int* nums = (int*)malloc(sizeof(int) * numsSize); 
    for(int i = 0 ; i < numsSize ; i++) {
        scanf("%d",&nums[i]);
    }
    printf("%d",maxSubArray(nums,numsSize));
    return 0;
}