《算法入门竞赛经典》（第八章）8.1

最大连续和
三种方法：
1，暴力枚举（三重for循环）n^3;
2，记录从开始到每个点的总和，通过两个点的总和相减来求各段区间的长度n^2
3，利用分治的思想，求左边L的最大值和右边R的最大值，L+R就为最大连续和nlogn

1，第一种

#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>
#include<time.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int a[100005];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int sum = a[1];
    int temp;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            temp = 0;
            for (int k = i; k <= j; k++)
            {
                temp += a[k];
            }
            sum = max(sum, temp);
        }
    }
    printf("%d\n", sum);
    return 0;
}

2，第二种

#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>
#include<time.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int a[100005];
int s[100005];
int main()
{
    int n;
    cin >> n;
    s[0] = 0;
    int sum=-INF;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            sum=max(sum, s[j]-s[i-1]);//千万不能写成s[j]-s[i]因为如果全是负数，如-1，-1，-1，-1这样写求出来是0；
        }
    }
    printf("%d\n", sum);
    return 0;
}

3，分治法
1，划分问题
2，递归求解
3，合并问题

#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>
#include<time.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int a[100005];
int maxsum(int *a, int x, int y)
{
    if (y - x == 1)
    {
        return a[x];
    }
    int m = x + (y - x) / 2;
    int Max = max(maxsum(a, x, m), maxsum(a, m, y));
    int temp, L, R;
    temp = 0;
    L = a[m - 1];
    for (int i = m - 1; i >= x; i--)
    {
        L = max(L, temp += a[i]);
    }
    temp = 0;
    R = a[m];
    for (int i = m; i <y; i++)
    {
        R = max(R, temp += a[i]);
    }
    return max(Max, L + R);
}
int main()
{
    int n;
    cin >> n;
    int sum;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sum = maxsum(a, 1, n+1);
    printf("%d\n", sum);
    return 0;
}