最大子段和问题

问题描述:

给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。如果该序列的所有元素都是负整数时定义其最大子段和为0。

例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4]。

问题分析:

最直接的想法就是利用遍历法遍历所有的可能,然后找到最大的那个,显然这不是一种有效的方法,但切实可行。在第二章的时候学习了分治方法,想到也可以把序列拆分成两部分,答案就在前半段或者后半段或者是穿过两段中间的部分。

暴力遍历法:

就是找到所有可能的结果然后再判断找到符合要求的那一个。首先我们需要一个循环来遍历从第一个位置到最后一个位置:for(int i = 0;i < n; i++),然后还需要一个内层循环来遍历从当前位置到最后一个位置,来分别计算当前的最大子段和:

int maxSum(int n, int[] a, int besti, int bestj) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int thissum = 0;        
        
        for (int j = i; j <= n; j++) {
            thissum += a[j - 1];
            if (thissum > sum) {
                sum = thissum;
                besti = i;
                bestj = j;
            }   // end if
        }   // end inner for
        
    }   // end out for
    
    return sum;
}   // end maxSum

很明显该算法的计算时间是O(n²)。

分治法:

针对最大字段和这个具体问题本身的结构,还可以从算法设计的策略上对上述O(n²)计算时间算法加以更深刻的改进。

如果将给定的序列a[1..n]分成长度相等的两段a[1..n/2]和a[n/2+1:n],分别求出这两段的最大字段和。则该给定序列的最大字段和有三种情行:

  • ①和a[1..n/2]的最大字段和相同。
  • ②和a[n/2+1:n]的最大字段和相同。
  • ③最大字段和包含两部分,一部分在a[1..n/2]中,另一部分在a[n/2+1..n]中。

前两种情形我们可以用递归方法求出,第三种情形可以分别求出两部分的最大字段和值再相加(注:a[1..n/2]这部分求最大字段和要以a[n/2]结束,a[n/2+1..n] 这部分求最大字段和要以a[n/2+1]开始)。序列的最大字段和即为这三种情形的最大值。

static int maxSubSum(int[] a, int left, int right) {
    int sum = 0;
    if (left == right) {
        sum = a[left - 1] > 0 ? a[left - 1] : 0;
    } else {
        int center = (left + right) / 2;
        int leftSum = maxSubSum(a, left, center);
        int rightSum = maxSubSum(a, center + 1, right);

        int s1 = 0;
        int lefts = 0;
        for (int i = center; i >= left; i--) {
            lefts += a[i - 1];
            if (lefts > s1) s1 = lefts;
        }

        int s2 = 0;
        int rights = 0;
        for (int i = center + 1; i <= right; i++) {
            rights += a[i - 1];
            if (rights > s2) s2 = rights;
        }

        sum = s1 + s2;
        if(sum < leftSum) sum = leftSum;
        if(sum < rightSum) sum = rightSum;
    }   // end if

    return sum;
}   // end maxSubSum

该算法的计算时间为O(nlogn)。

动态规划算法:

如果我们定义一个b[j]表示到当前位置为止,最大的字段和,那么事情就会变得更加简单:

static int maxSum(int n, int[] a) {
    int sum = 0, b = 0;
    for (int i = 1; i <= n; i++) {
        if (b > 0) b += a[i - 1];
        else b = a[i - 1];
        if (b > sum) sum = b;
    }

    return sum;
}

该算法的计算时间需要O(n)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏kalifaの日々

POJ2431-最优队列(最小堆)解法

这道题有一个坑,就是给出的加油站到终点的距离不一定是降序排列好了的。 所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>...

36370
来自专栏编程

从机器学习学python(一)——numpy中的shape、tile、argsort

从机器学习学python(一) ——numpy中的shape、tile、argsort (原创内容,转载请注明来源,谢谢) 注:本系列是我在学习机器学习过程中,...

20450
来自专栏蜉蝣禅修之道

基于Huffman编码的压缩软件的Python实现

24640
来自专栏kalifaの日々

C++构造无向图&求最短路径源码

用vector<edge> es[MAX]表示点,每个点队列里放着点的相邻边和到边的距离。 以下源码经过测试可运行 #include <iostream> #i...

32950
来自专栏数据结构与算法

1807. [NOIP2014]寻找道路P2296 寻找道路

题目描述 在有向图G 中,每条边的长度均为1 ,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件: 1 .路径上的所有点的出边所指向的点...

31560
来自专栏个人分享

调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相...

13830
来自专栏小L的魔法馆

C++创建学生类练习

37360
来自专栏Python小屋

Python从序列中选择k个不重复元素

集合中的元素不允许重复,Python集合的内部实现为此做了大量相应的优化,判断集合中是否包含某元素时比列表速度快很多。下面的代码用于返回指定范围内一定数量的不重...

35960
来自专栏烂笔头

Python正则表达式:最短匹配

目录[-] 最短匹配应用于:假如有一段文本,你只想匹配最短的可能,而不是最长。 例子 比如有一段html片段,<a>this is first label<...

45170
来自专栏ACM算法日常

leetcode题解 | 78. 子集

这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

17430

扫码关注云+社区

领取腾讯云代金券