首页 > 代码库 > 最大连续和的方法总结

最大连续和的方法总结

最大连续和的方法总结

第一种:暴力。复杂度O(n^3)。用两个循环枚举起点和终点,然后中间再放一个循环,计算这个起点到终点的连续和。

伪代码:
    max = -INF;
    s[maxn];

    for i in range(1, len):
        for(j in range(i, len)):
            sum = 0;
            for (k in range(i, j)):
                sum += s[k];
            else:
                max = Max(max, sum);
        else:;
    else:
        return max;

第二种:预处理 + 暴力枚举起点终点。复杂度O(n^2)。和第一个类似,只是一开始用sum[i],来储存从1到i的连续和。这样就可以去掉第三层的循环,直接用sum[end] - sum[begin]得到。

伪代码:
    max = -INF;
    s[maxn], sum[maxn];

    sum[0] = 0;
    for i int range(1, len):
        sum[i] = sum[i - 1] + s[i];
    else:;

    for i in range(1, len):
        for j int range(i, len):
            max = Max(max, sum[j] - sum[i - 1]);
        else:;
    else:
        return max;

第三种:分治法, 复杂度O(n*log(n))。思路是将长度为len的序列划分左右两个左闭右开的区间[l,m) [m, r),然后递归求出左边的区间的最大连续和,再求出右边的最大连续和,最后在求出跨中点m的最大连续和,这个区间的最大连续和就在这三者之中。将每个区间都划分成子问区间,直到区间只有一个数的时候停止。注意:两个区间不能同时拥有同一个元素,这样在后面的区间再划分的时候会出错(划分成单个元素区间的时候会发现每个元素都多了一个),这也是要左闭右开区间的原因。

伪代码:
    l = 1;
    r = len + 1;
    function maxsum (l, r) 
        if r - l == 1:    return s[l];

        m = (l + r) / 2;
        //左子区间
        maxLp = maxsum(l, m);
        //右子区间
        maxRp = maxsum(m, r);
        max = Max(maxLp, maxRp);

        //中间的跨越中点m的区间
        sumLp = s[m - 1];
        sum = 0;
        for i in range(m - 1, l)://i--
            sum += s[i];
            maxLp = Max(maxLp, sum);
        else:;

        sumRp = s[m];
        sum = 0;
        for i in range(m, r - 1)://i++
            sum += s[i];
            maxRp = Max(maxRp, sum);
        else:;

        return Max(max, maxRp + maxLp);
    end function

第四种:累积遍历算法(1),复杂度O(n).从左到右用一个Sum变量累计,当Sum<0的时候就令Sum = 0,再去加上后面的数,并且在这个遍历的过程中记录下Sum的最大值。换句话说:用这个Sum将这个序列分段,如果前面的连续和比0还小的话,那么加上后面的数倒还没有后面的数自己作为开头的连续和大,所以就让Sum = 0.这样才可能产生比前面的连续和更大的值。

伪代码:
    s[maxn];
    max = sum = s[1];

    for i in range(2, len):
        if sum < 0:
            sum = s[i];
        else:
            sum += s[i];
        max = Max (max, sum);
    else: return max;

第五种:累积遍历算法(2),复杂度O(n).同样也是用一个变量Sum来累计,只是这里用一个MinPart来保存前面从1开始的最小的连续和。因为这个序列的所有值的和是确定的,那么只要取得了前面的最小连续和,因为总值是固定的,后面的就是最大的连续和,也就是遍历过程中Sum - MinPart的最大值。

伪代码;
    s[maxn];
    MinPart = sum = 0;//注意开头可能是正数
    max = s[1];

    for in range(1, len):
        sum += s[i];
        max = Max (sum - MinPart);
        MinPart = Min (MinPart, sum);
    else: return max;

第六种:动态规划,复杂度O(n)。和第四种的想法是类似的,只是这里是开一个sum[maxn]的数组。状态转移方程:sum[i] = Max(sum[i - 1] + s[i], s[i]);

伪代码:
    sum[maxn],s[maxn];
    max = sum[1] = s[1];//只有一个数的情况下只能取这个数

    for in range(2, len):
        sum[i] = Max (sum[i - 1] + s[i], s[i])
        max = Max (max, sum[i]);
    else: return max;

接下来是UVA507的题目的四种解法,因为前两种比较简单而且放在这题会超时就不写了。这题需要给出上下界的。

分治法
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2e4 + 5;
int n, s[maxn];

struct Ans {

    int v, l, r;
    Ans () {}
    Ans (int v, int l , int r) : v(v), l(l), r(r){}
    void set (int v, int l, int r) {
        this->v = v;
        this->l = l;
        this->r = r;
    }
};

Ans maxsum (int l, int r) {

    if (r - l == 1) 
        return Ans(s[l], l, l);

    Ans max_sum;
    int m = l + (r - l)/2;
    Ans Lmax = maxsum(l, m);
    Ans Rmax = maxsum(m, r);    
    if (Lmax.v > Rmax.v) 
        max_sum = Lmax;
    else if (Lmax.v < Rmax.v)
        max_sum = Rmax;
    else  {    
        if (Lmax.r - Lmax.l < Rmax.r - Rmax.l)
            max_sum = Rmax;
        else
            max_sum = Lmax;
    }

    Ans Lp(s[m - 1], m - 1, m - 1), Rp(s[m], m, m);    
    int tmp = 0;
    for (int i = m - 1; i >= l; i--) {
        tmp += s[i];
        if (tmp >= Lp.v) 
            Lp.set(tmp, i, m - 1);
    }

    tmp = 0;
    for (int i = m; i < r; i++) {
        tmp += s[i];
        if (tmp >= Rp.v) 
            Rp.set(tmp, m, i);
    }

    Ans Center(Lp.v + Rp.v, Lp.l, Rp.r);
    if (Center.v > max_sum.v) 
        max_sum = Center;
    else if (Center.v == max_sum.v) {
        int dis1 = Center.r - Center.l;
        int dis2 = max_sum.r - max_sum.l;
        if (dis1 > dis2 || (dis1 == dis2 && Center.l < max_sum.l))
            max_sum = Center;
    }

    return max_sum;
}

int main () {

    int T;
    scanf ("%d", &T);

    for (int cas = 1; cas <= T; cas++) {  

        scanf ("%d", &n);
        for (int i = 0; i < n - 1; i++)
            scanf ("%d", &s[i]);

        Ans result = maxsum(0, n - 1);
    //    printf ("%d\n", result.v);
        if (result.v < 0)  
            printf ("Route %d has no nice parts\n", cas);  
        else  
            printf ("The nicest part of route %d is between stops %d and %d\n", cas, result.l + 1, result.r + 2);  
    }  
    return 0;  
}
累计遍历法(1):
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2e4 + 5;
int n, s[maxn];

int solve (int& l, int& r) {

    int Max_num, sum;
    int tmp;

    l = r = tmp = 1; //border
    Max_num = sum = s[0];

    for (int i = 1; i < n - 1; i++) {

        if (sum < 0) {
            sum = s[i];
            tmp = i + 1;
        } else
            sum += s[i];

        if (sum > Max_num) {
            Max_num = sum;
            l = tmp;
            r = i + 1;
        } else if (sum == Max_num) {
            if (r - l < i + 1 - tmp || ((r - l) == (i + 1 - tmp) && tmp < l)) {
                l = tmp;
                r = i + 1;
            }
        }
    }

    return Max_num;
}

int main () {

    int T, l, r;
    scanf ("%d", &T);

    for (int cas = 1; cas <= T; cas++) {  

        scanf("%d", &n);  
        for (int i = 0; i < n - 1; i++)  
            scanf ("%d", &s[i]);  

        int ans = solve(l, r);  
//        printf ("%d\n", ans);
        if (ans < 0)  
            printf ("Route %d has no nice parts\n", cas);  
        else  
            printf ("The nicest part of route %d is between stops %d and %d\n", cas, l, r + 1);  
    }  
    return 0;  
}
累积遍历法(2):
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2e4 + 5;
int n, s[maxn];

int solve (int& l, int& r) {

    int Min_sum, sum, Max_sum;
    int tmp;

    tmp = 0; //border
    l = r = 1;
    sum = Min_sum = 0;
    Max_sum = s[0];

    for (int i = 0; i < n - 1; i++) {

        sum += s[i];
        if (sum - Min_sum >= Max_sum) {
            if (sum - Min_sum > Max_sum) {
                Max_sum = sum - Min_sum;
                l = tmp + 1;
                r = i + 1;
            } else if (sum - Min_sum == Max_sum) {    
                if (i - tmp > r - l) {
                    l = tmp + 1;
                    r = i + 1;
                }
            }
        }

        if (sum < Min_sum) {
            Min_sum = sum;
            tmp = i + 1;
        }
    }

    return Max_sum;
}

int main () {

    int T, l, r;
    scanf ("%d", &T);

    for (int cas = 1; cas <= T; cas++) {  

        scanf("%d", &n);  
        for (int i = 0; i < n - 1; i++)  
            scanf ("%d", &s[i]);  

        int ans = solve(l, r);  
//        printf ("%d\n", ans);
        if (ans < 0)  
            printf ("Route %d has no nice parts\n", cas);  
        else  
            printf ("The nicest part of route %d is between stops %d and %d\n", cas, l, r + 1);  
    }  
    return 0;  
}
动态规划:
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2e4 + 5;
int n, s[maxn], sum[maxn];

int solve (int& l, int& r) {

    int Max_sum, tmp;
    Max_sum = sum[0] = s[0];
    l = r = tmp = 1;

    for (int i = 1; i < n - 1; i++) {

        if (sum[i - 1] + s[i] < s[i]) {
            sum[i] = s[i];
            tmp = i + 1;
        } else 
            sum[i] = sum[i - 1] + s[i];
        //max
        if (Max_sum <= sum[i]) {

            if (Max_sum < sum[i]) {
                Max_sum = sum[i];
                l = tmp;
                r = i + 1;
            } else if (Max_sum == sum[i] && (i + 1 - tmp > r - l)) {
                l = tmp;
                r = i + 1;
            }
        }
    }
    return Max_sum;
}

int main () {

    int T, l, r;
    scanf ("%d", &T);

    for (int cas = 1; cas <= T; cas++) {  

        scanf ("%d", &n);
        for (int i = 0; i < n - 1; i++)
            scanf ("%d", &s[i]);

        int ans = solve(l, r);
        if (ans < 0)  
            printf ("Route %d has no nice parts\n", cas);  
        else  
            printf ("The nicest part of route %d is between stops %d and %d\n", cas, l, r + 1);  
    }  
    return 0;  
}

感谢GG大神:参考博客

最大连续和的方法总结