AOJ 807.算法期末考试C(最大子序列和)

160

题目


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[],其lr之间的最大子序列和有如下可能
对于mid=(l+r)/2
  • 最大子序列和完全在mid左侧
  • 最大子序列和完全在mid右侧
  • 最大子序列和经过mid

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

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

递归的终点是| 545d7a4749a83de72aaf7696b10ca0f016 |。此时,函数的意义不存在,返回值没有意义。
我们可以返回| 545d7a4749a83de72aaf7696b10ca0f018 |来确保不会对数据造成影响(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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论