最大子段和(不同解法)

问题描述

最大子段和:给定n个整数(可以有负数),求出其最大连续的子段的和,如果全部都为负数,那么结果为0。

穷举法

思想

将所有子段可能的情况穷举出来,分别求出子段和,得到最大值,如果最大值为负数,取最大值为0.

代码实现

时间复杂度

O(n^2 )

分治算法

思想

将a[0,n]分为a[0,n/2]和a[n/2+1,n],a[0,n]有三种情况:

  1. 第一种情况与a[0,n/2]相同;
  2. 第二种情况与a[n/2+1,n]相同;
  3. 第三种情况是a[0,n/2]情况与a[n/2+1,n]情况的和。
    所以实现代码时,只要通过计算第三种情况与第一、二种情况的大小,就可以得到最大子段和。

    代码实现

    用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
    #include<iostream>
    using namespace std;
    int MaxSub(int v[], int l, int r);

    int main()
    {

    int v[10] = {1, 2, -4, 4, 5, -6, 7, 8, -9, 0};
    int l = 0, r = 9;
    cout << MaxSub(v, l, r) <<endl;
    return 0;
    }

    int MaxSub(int v[], int l, int r)
    {

    if(l == r)
    {
    return v[l] > 0 ? v[l] : 0;
    }
    int m = (l + r) / 2;
    int lsum = MaxSub(v, l, m);
    int rsum = MaxSub(v, m + 1, r);

    int maxl = 0;
    int sum = 0;
    for(int i = m; i >= l; i--)
    {
    sum += v[i];
    if(sum > maxl)
    {
    maxl = sum;
    }
    }

    int maxr = 0;
    sum = 0;
    for(int j = m+1; j <= r; j++)
    {
    sum += v[j];
    if(sum > maxr)
    {
    maxr = sum;
    }
    }
    sum = maxl + maxr;
    if(lsum > sum)
    {
    sum = lsum;
    }
    if(rsum > sum)
    {
    sum = rsum;
    }
    return sum;
    }

时间复杂度

O(nlog(n))

动态规划实现

思想

数组从头开始遍历,逐个累加,如果累加的和小于0,则和置为0,继续累加,记录最大sum,返回最大的sum。

代码实现

用C++实现,如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;

int main()
{

int a[10] = {1, 2, -4, 4, 5, -6, -7, 8, -9, 0};
int i, max = 0, sum = 0;
int len = sizeof(a) / sizeof(a[0]);
for(i = 0; i < len; i++)
{
if(sum < 0)
{
sum = 0;
}
sum += a[i];
max = sum > max ? sum : max;
}
cout << max << endl;
return 0;
}

复杂度

O(n)