动态规划---例题3.最大子段和问题_最大子段和问题,比较三重循环,分治法和动态规划算法的效果,测试数据: 1) (-2,11,-

本题与力扣主站53题 — 最大子序和相同.

一.问题描述

给定n个整数（可能有负数）组成的序列a1,a2,…an, 求子段和ai+ai+1+…+aj的最大值。
当所有整数均小于零时，定义其子段和为0。
最大值为max{0, maxΣak}
例：(-2, 11, -4, 13, -5, -2)的最大子段和为20

二.解题思路

1.朴素暴力
我们使用数组a存放n个整数，sum、besti、bestj分别存放最大子段和及其始末下标。
时间复杂度: T(n) = O(n^3)

int MaxSum(int n, int *a, int &besti, int &bestj)
{
    int sum = 0;
    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++)  //i,j边界确定下来
        {
            int thissum = 0;
            for(int k=i; k<=j; k++) thissum += a[k];  //(用k来遍历a[i,j]求和)每次k只是加一,所以重复计算了a[i]~a[j]的和
            if(thissum > sum)
            {
                sum = thissum;
                besti = i;
                bestj = j;
            }
        }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

对上述方法的改进:
我们用k来遍历a[i…j]求和,每次k只是加一,所以重复计算了a[i]~a[j]的和.故我们可以省略一个循环,每次j++后,只要把最后一个a[k] (此时k=j)加上就好.
时间复杂度: T(n) = O(n^2)

int MaxSum2(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];
            if(thissum > sum)
            {
                sum = thissum;
                besti = i;
                bestj = j;
            }
        }
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.分治算法

将a[1:n]分为a[1:n/2]和a[n/2+1:n]两部分,一共分三种情形：

• 最大子段和在左半部分，比如LS
• 最大子段和在右半部分，比如RS
• 最大子段和跨越两部分，为S1+S2，并且左半部分的最右端元素一定在S1中，右半部分的最左端元素一定在S2中。

最大子段和等于: Max(LS, RS, S1+S2)
时间复杂度:T(n) = O(n log n)

int MaxSubSum13(int *a, int left, int right)
{
    int sum = 0;
    if(left == right) sum = a[left]>0 ? a[left]:0;
    else
    {
        int center = (left+right)/2;
        int leftsum = MaxSubSum13(a, left, center);
        int rightsum = MaxSubSum13(a, center+1, right);
        
        int s1 = 0;
        int lefts = 0;
        for(int i=center; i>=left; i--)  //从center位置往左和往右分别找到最大值
        {
            left += a[i];
            if(lefts > s1) s1 = lefts;
        }
        int s2 = 0;
        int rights = 0;
        for(int i=center+1; i<=right; i++)
        {
            right += a[i];
            if(rights > s2) s2 = rights;
        }
        sum = s1+s2;
        if(sum<leftsum) sum = leftsum;
        if(sum<rightsum) sum = rightsum;
    }
    return sum;
}
int MaxSum13(int n, int *a)
{
    return MaxSubSum13(a, 1, n);
}
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

计算时间：递归方程

• T(n)=O(1) n<=C

• T(n)=2T(n/2)+O(n) n > C

  故T(n)=O(n logn)

3.动态规划(重点)

假设nums数组长度为n, 我们用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，
那么很显然我们要求的答案就是：max(0<i<n){f(i)}

因此我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢？
我们可以考虑 nums[i], 单独成为一段还是加入f(i-1) 对应的那一段.这取决于 nums[i] 和 f(i-1) + nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程:

• f(i) = max(nums[i], f(i-1) + nums[i]) 1<=i<=n

时间复杂度: T(n) = 0(n)

int maxSubArray3(vector<int>& nums)
{
    if(nums.size()==0) return {};
    int n = nums.size();
    int pre = 0;
    int maxSum = nums[0];
    for(int i=0; i<n; i++)   //for(const auto   & x : nums) 
    {
        pre = max(pre+nums[i], nums[i]);
        maxSum = max(pre, maxSum);
    }
    return maxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

本篇文章参考我的老师毕方明《算法设计与分析》课件.

欢迎大家访问我的个人博客 — 乔治的编程小屋,和我一起为大厂offer 努力吧!