分治法解决最大子段和问题（要求输出起点和终点）_如果想要输出最大子段的具体情况应该怎么办

问题：用分治算法解决最大子段和问题并输出最大子段和的起点，终点位置

一、思路

用分治法求解这个问题 。

在数组的 center = (right-left)/2+left 位置处分开。形成两个子数组。

那么，最大子段和 可能出现在三个位置：

a.可能出现在 左 子数组

b. 可能出现在 右子数组

c.可能出现在 过center的 中间某部分 元素 组成的子数组。

下面考虑 三种情况的计算方法：

第一种情况： 计算 left 到 center 的最大和，记作 leftSum

第二种情况： 计算从 center+1 到 right的最大和，记作 rightSum

第三种情况： 跨边界的和。 以center为中心分别向两边计算和。

a.从 center出发，每次向左边扩张一步，并且记录当前的值S1，如果当前的和比上次的和大，就更新S1，一直向左扩张到位置 Left。

b.从 center+1出发，每次扩张一步，计算当前的和 为S2，如果当前的值比上次的和 大，那么，就更新S2的值，一直向右扩张到位置Right。

c.计算过center的连续值的和，S1+S2的值 Sum。 这个就是跨边界的和。

上面三种情况考虑计算完成后，最后一步就是，比较三个值中的最大值，取最大值就可以了。

二、代码

代码如下（示例）：

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
int MaxSubSum(int *a,int left,int right,int &p,int &q)
{
    int sum=0;int p1,p2,p3,q1,q2,q3;
    if(left==right)
    {
        sum=a[left]>0?a[left]:0;
        p=left;q=left;
    }
    else
    {
        int center=(left+right)/2;
        int leftsum=MaxSubSum(a,left,center,p1,q1);
        int rightsum=MaxSubSum(a,center+1,right,p2,q2);
        int s1=0;
        int lefts=0;
        for(int i=center;i>=left;i--)
        {
            lefts+=a[i];
            if(lefts>s1)
            {
                s1=lefts;p3=i;
            }
        }
        int s2=0;
        int rights=0;
        for(int i=center+1;i<=right;i++)
        {
            rights+=a[i];
            if(rights>s2)
            {
                s2=rights;q3=i;
            }
        }
        sum=s1+s2;
        p=p3;q=q3;
        if(sum<leftsum)
        {
            sum=leftsum;
            p=p1;q=q1;
        }
        if(sum<rightsum)
        {
            sum=rightsum;
            p=p2;q=q2;
        }
    }
    return sum;
}
int main()
{
    srand((int)time(0));
    int n=20000,a[100000],p,q,sum=0;
    for(int i=1;i<=n;i++)
    {
        int t=rand()%2;
        if(t==0)
            a[i]=rand()%20+1;
        else a[i]=-(rand()%20+1);
        //cout<<a[i]<<" ";
    }
    //cout<<endl;
    cout<<"最大子段和为："<<MaxSubSum(a,1,n,p,q)<<endl;
    cout<<"起始位置："<<p<<" ";
    cout<<"终止位置："<<q<<endl;
    for(int i=p;i<=q;i++) sum+=a[i];
    cout<<sum<<endl;
}

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

三、运行截图