前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【题解】最大子段和

【题解】最大子段和

作者头像
fishhh
发布2022-08-31 14:46:31
2660
发布2022-08-31 14:46:31
举报
文章被收录于专栏:OI算法学习笔记OI算法学习笔记

题目描述

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

输入格式

第一行是一个整数,表示序列的长度 n。

第二行有 n 个整数,第 i 个整数表示序列的第 i 个数字 aia_iai​。

输出格式

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

输入输出样例

输入 #1

代码语言:javascript
复制
7
2 -4 3 -1 2 -4 3

输出 #1

代码语言:javascript
复制
4

说明/提示

样例 1 解释

选取 [3,5] 子段 {3,−1,2},其和为 4。

数据规模与约定
  • 对于 40% 的数据,保证
  • 对于 100% 的数据,保证

题目分析

尺取法的本质是对连续区间的维护,被维护的区间符合某种条件。右指针相当于把元素加入到这个区间,左指针相当于把元素从区间内去除。除了之前题目中的双指针,骑士也能够用队列来进行处理,又或者是具有相似概念的东西。

仔细阅读题目,可发现题目要求的是连续且非空的最大子段和。

若用暴力方式处理复杂度为

根据数据范围明显不可取。此时,可发现又是一个对连续区间的维护问题,那么我们尝试从其他的角度进行思考。

该区间元素必须连续,那么当碰见一个新的元素,无非出现两种情况:

  1. 该元素与之前的连续区间加起来的和比较大
  2. 该元素与之前的连续区间加起来的和还没有这个元素本身大

如果是情况1,那么连续区间总和就加上新增元素。而如果是情况2,则将该元素作为新的连续区间总和。在过程中再不断更新最大连续区间和即可。

由于只需遍历每个元素一次,时间复杂度为O(n)。

代码实现

代码语言:javascript
复制
#include <iostream>
#include <cstdio>
using namespace std;
int a;
/*
连续序列和
1. 当前元素
2. 和前面的一段组成新序列
*/
int main(){
    int n;
    int sum=0;//连续序列和
    int ans=-1e9;//最大连续序列和
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        if(sum+a<a){//判断是a与前面的连续序列加起来大还是单独一个元素更大
            sum=a;//单独的元素更大
        }else{
            sum+=a;//加起来更大
        }
        ans=max(ans,sum);//更新过程中的最大连续序列和
    }
    cout<<ans;//输出答案
    return 0;
}

Q.E.D.

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 输入格式
  • 输出格式
  • 输入输出样例
  • 说明/提示
    • 样例 1 解释
      • 数据规模与约定
      • 题目分析
      • 代码实现
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档