题目

Description

给一串整数a[1..n]，求出其和最大的子序列，即找出1<=i<=j<=n（1<=n<=50000），使a[i]+a[i+1]+…+a[j]最大。

Input

多组输入，EOF结束，每组输入包含两行，第一行有一个数字n表示有n个数字，第二行有n个数字，每个数字的绝对值小于1000。

Output

对于每组输入，输出最大子序列和

Sample Input

5
2 -3 -5 7 6
5
1 4 6 -9 10

Sample Output

13
12

题解

采用递归的思路来写

对于一列数a[]，其l到r之间的最大子序列和有如下可能
对于mid=(l+r)/2

• 最大子序列和完全在mid左侧
• 最大子序列和完全在mid右侧
• 最大子序列和经过mid

那么，只需要用递归实现它即可。
显然，前两种方法直接继续递归即可
而最后一种可以分别向mid左侧和右侧进行循环，将两边所能达到的最大值与mid对应的值三个数相加

返回这三种情况的最大值即可

递归的终点是l>r。此时，函数的意义不存在，返回值没有意义。
我们可以返回-INF来确保不会对数据造成影响(INF是无穷大，或者说当前整数类型所能表示的最大数)
当l==r时，我们应该返回这个相同的值

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
const int INF = 2<<30-1;
const int maxn = 50005;
int a[maxn];
 
int dfs(int *a,int l,int r) {
    if(l == r)
        return a[l];
    if(l > r)
        return -INF;
 
    int mid = (l + r) / 2;
    int Max;
    int ans;
    //中间
    ans = 0;
    int maxl = 0;
    for(int i = mid - 1;i >= l;i--) {
        ans += a[i];
        if(ans > maxl)
            maxl = ans;
    }
    ans = 0;
    int maxr = 0;
    for(int i = mid + 1;i <= r;i++) {
        ans += a[i];
        if(ans > maxr)
            maxr = ans;
    }
    Max = maxl + a[mid] + maxr;
 
    //左侧
    Max = max(Max,dfs(a,l,mid - 1));
 
    //右侧
    Max = max(Max,dfs(a,mid + 1,r));
 
    return Max;
}
 
bool Do() {
    int n;
    if(scanf("%d",&n) == EOF)
        return false;
    for(int i = 0;i < n;i++)
        scanf("%d",&a[i]);
 
    printf("%d\n",dfs(a,0,n - 1));
    return true;
}
 
int main() {
    while(Do());
    return 0;
}