<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-10 11:31
点赞 评论 收藏
分享
点赞 评论 收藏
分享
05-29 20:34
门头沟学院 C++
KarlAllen:得做好直接春招的准备。学历差的话,一是面试要求会比学历好的严格不少,二是就算面试通过了也会被排序。总之暑期和秋招对于学历差的就是及其不友好
无实习如何秋招上岸
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

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