首页 > ACM题库 > 九度OJ > 九度-1527-首尾相连数组的最大子数组和[解题代码]
2013
12-13

九度-1527-首尾相连数组的最大子数组和[解题代码]

题目来源:淘宝2013年校园招聘一面面试题

题目描述:

给定一个由N个整数元素组成的数组arr,数组中有正数也有负数,这个数组不是一般的数组,其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组,其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j],现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值(如果数组中的元素全部为负数,则最大和为0,即一个也没有选)。

输入:

输入包含多个测试用例,每个测试用例共有两行,第一行是一个整数n(1=<n<=100000),表示数组的长度,第二行依次输入n个整数(整数绝对值不大于1000)。

输出:

对于每个测试用例,请输出子数组和的最大值。

样例输入:
6
1 -2 3 5 -1 2
5
6 -1 5 4 -7
样例输出:
10
14

cpp 代码如下:
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;

const int MAX=110000*2;

int sum[MAX];
struct Q
{
    int id,v;
}q[MAX];
int front;
int rear;
void push(int id,int v)
{
    rear++;
    q[rear].id=id;
    q[rear].v=v;
    while(rear-1>=front&&q[rear-1].v>q[rear].v)
    {
        rear--;
        q[rear]=q[rear+1];
    }
}
int query(int id)
{
    while(front<=rear&&q[front].id<id)
    {
        front++;
    }
    if(front>rear)return 0;
    return q[front].v;
}
int main()
{
    int n;
    int i;
    int CS=1;
    while(scanf("%d",&n)!=EOF)
    {
        sum[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&sum[i]);
            sum[i+n]=sum[i];
        }
        for(i=1;i<=2*n;i++)sum[i]+=sum[i-1];
        rear=-1;
        front=0;
        push(0,0);
        int ans=0;
        for(i=1;i<=2*n;i++)
        {
            int tmp=sum[i]-query(i-n+1);
            if(tmp>ans)ans=tmp;
            push(i,sum[i]);

        }
        printf("%d\n",ans);
    }
    return 0;
}
/**************************************************************
	Problem: 1527
	User: coder
	Language: C++
	Result: Accepted
	Time:90 ms
	Memory:3600 kb
****************************************************************/


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?