顺序表应用7：最大子段和之分治递归法

#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
int getmax(int s[], int l, int r)
{
    cnt++;
    if(l == r)//表示当前只剩下一个数字了，如果该数字小于0,则输出0，否则输出他的本身
    {
        if(s[l] < 0)
        {
            return 0;
        }
        else
        {
            return s[l];
        }
    }
    int leftmax, rightmax, Max;
    int mid;
    mid = (l + r) / 2;//找到中间的数字
    leftmax = getmax(s,l,mid);//获取到左边最大的数字
    rightmax = getmax(s,mid+1,r);//获取到右边最大的数字
    int suml = 0;
    int sum = 0;
    int sumr = 0;
    for(int i = mid; i >= l; i--)//找出左边最大的数字，赋值于suml
    {
        sum = sum + s[i];//代表左边数字的累加
        if(sum > suml)//判断是否加的是负数
        {
            suml = sum;
        }
    }
    sum = 0;
    for(int i = mid + 1; i <= r; i++)//找出右边最大的数字，赋值于sumr
    {
        sum = sum + s[i];//代表右边数字的累加
        if(sum > sumr)//判断是否加的是负数
        {
            sumr = sum;
        }
    }
    Max = suml + sumr;//这是一个整部分最大值
    Max = max(Max,leftmax);//找寻左边最大值和整部分最大值
    Max = max(Max,rightmax);//找寻右边最大值和整部分最大值
    return Max;
}
int main()
{
    int n;
    int sum = 0;
    int s[50010];
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        scanf("%d", &s[i]);
    }
    sum = getmax(s,0,n-1);
    printf("%d %d\n", sum, cnt);
    return 0;
}