循环数组最大子段和(动态规划)

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050

两种情况：

1 最大子段和没有循环

第i个位置的最大子段和由它i-1的最大子段和决定。dp[i-1]>=0，则dp[i]=dp[i-1]+a[i]；dp[i-1]<0，dp[i]=a[i]（本身）

2 最大字段和有循环

说明中间有一段字段和是负数，那么可以将所有数取相反数，算出相反数的最大字段和加到所有数的和上，就相当于和减去最小字段和为最大字段和

#include<iostream>
#include<algorithm>
#define MAXLEN 50005
#define LL long long
using namespace std;

LL Maximum_Interval_Sum(int a[], int len)
{
    LL dp[MAXLEN] = { 0 }, maxn = a[0];
    dp[0] = a[0];
    for (int i = 1; i < len; i++)
    {
        if (dp[i - 1] >= 0)
            dp[i] = a[i] + dp[i - 1];
        else
            dp[i] = a[i];
        maxn = max(dp[i], maxn);
    }
    return maxn;
}
int main()
{
    int n, a[MAXLEN], b[MAXLEN];
    LL sum = 0;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        b[i] = -a[i];
        sum += a[i];
    }
    LL mid = Maximum_Interval_Sum(a, n);
    LL head_tail = sum + Maximum_Interval_Sum(b, n);
    cout << max(mid, head_tail);
    //system("pause");
    return 0;
}