<span>最大子列和</span>

题目描述

给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数,表示序列的长度 n。
第二行有 n 个整数,第 i个整数表示序列的第 i个数字 \(a_i\)

输出格式

输出一行一个整数表示答案。

输入输出样例

输入

7
2 -4 3 -1 2 -4 3

输出

4

数据范围

对于 40% 的数据,保证 n \(\leq\) 2 \(\times\) \(10^3\)
对于 100% 的数据,保证 n \(\leq\) 2 \(\times\) \(10^5\),-\(10^4\) \(\leq\) \(a_i\) \(\leq\) \(10^4\)

思路1(暴力求解):

计算出每个子序列的和再选出其中最大的那一个。(注意:根据这道题目的数据范围来说,这个思路会TLE)

#include<iostream>
#include<vector>
using namespace std;
typedef long long int ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> a(n+5),s(n+5);
    for(int i=1;i<=n;i++)
    {
         cin>>a[i];
         s[i]=s[i-1]+a[i];//前缀和处理一下
    }
    ll maxSum=a[1];
    for(int i=1;i<=n;i++)//i代表子序列的左端点
    {
        for(int j=i;j<=n;j++)//j代表子序列的右端点
           if(s[j]-s[i-1]>maxSum)//s[j]-s[i-1]=a[i]+a[i+1]+...+a[j]
           maxSum=s[j]-s[i-1];
    }
    cout<<maxSum<<endl;
    return 0;
}

思路2(分治思想):

将一个序列分成两段,分别求两个子序列的最大子序列和,再求出越过序列分界点的最大子序列和,那么序列的最大子序列和一定是三个值中的最大值。
1)如何求两个子序列的最大子序列和?
答:将这两个子序列分别再分成两段,当子序列中只有一个数字的时候最大子列和就是这个数字,再递归返回就可以了。
2)如何求出越过序列分界点的最大子序列和?
答:从分界点左端扫描,维护出一个leftMax;同理,右端维护出一个rightMax。leftMax+分界点处的值+rightMax即为所求。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
int a[200005];
ll cal(int l,int r)
{
    if(l>=r)
    return a[l];
    int mid=(l+r)>>1;
    ll leftMax=0,rightMax=0,thisSum=0;
    for(int i=mid-1;i>=l;i--)
    {
        thisSum+=a[i];
        if(thisSum>leftMax)
        leftMax=thisSum;
    }
    thisSum=0;
    for(int i=mid+1;i<=r;i++)
    {
        thisSum+=a[i];
        if(thisSum>rightMax)
        rightMax=thisSum;
    }
    return max(max(cal(l,mid),cal(mid+1,r)),leftMax+a[mid]+rightMax);//求出cal(l,mid),cal(mid+1,r),leftMax+a[mid]+rightMax三者之间的最大值
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
         cin>>a[i];
    }
    cout<<cal(1,n)<<endl;
    return 0;
}

思路3(动态规划):

根据题意我们可以得出以下结论:
1)第一个数字为有效序列。
2)如果一个数加上上一个有效序列得到的结果比这个数大(即前面的子列和>0),那么该数也属于这个有效序列。
3)如果一个数加上上一个有效序列得到的结果比这个数小(即前面的子列和<0),那么这个数单独成为一个新的有效序列,我们需要将前面的子列和抛弃,即重新归0。
综上,我们可以得出以下代码:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,x;
    ll thisSum=0,maxSum=-10005;
    cin>>n;
    while(n--)
    {
        cin>>x;
        thisSum+=x;//向右累加
        maxSum=max(maxSum,thisSum);//发现更大和则立即更新当前结果
        if(thisSum<0)//如果当前子列和为负,
        thisSum=0;//则不可能使后面的子列和更大,抛弃它
        
    }
    cout<<maxSum<<endl;
    return 0;
}
全部评论

相关推荐

07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务