• 秋招每日一题T28——最大连续子序列


    题目描述

    给定 K 个整数的序列 {N0,N1,…,NK−1},其任意连续子序列可表示为 {Ni,Ni+1,…,Nj},其中 0≤i≤j

    最大连续子序列是所有连续子序列中元素和最大的一个,例如给定序列 {−2,11,−4,13,−5,−2},其最大连续子序列为 {11,−4,13} ,最大和为 20。

    编写程序得到其中最大子序列的和并输出该子序列的第一个和最后一个元素的下标。

    输入格式
    输入包含多组测试数据。

    每组数据占 2 行,第 1 行给出正整数 K。

    第 2 行给出 K 个整数 N1,…,NK。

    输出格式
    每组数据输出一行结果,包含最大子序列的和以及子序列的第一个下标 i 和最后一个元素的下标 j。

    所有元素下标为 0∼K−1。

    如果最大子序列不唯一,则选择 i 最小的那个子序列,如果仍不唯一,则选择 i 最小的子序列中 j 最小的那个子序列。

    若所有 K 个元素都是负数,则定义其最大和为 0,输出 0 0 0。

    数据范围
    1≤K≤105,
    −10000≤Ni≤10000,
    输入最多包含 10 组数据。

    在这里插入图片描述

    思路

    〇本题来自中南大学的考研机试题。
    ①题目是裸的DP模板题,但是要同时输出最大连续子序列的左右边界,这个确实卡了一会儿。
    ②当前的f[i]为局部最优时,更新总和res和左右边界l和r即可,仍是dp的思路。

    代码

    #include 
    #include 
    #include 
    using namespace std;
    const int maxn = 1e5 + 5;
    int a[maxn] = {0},f[maxn] = {0};
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	int n;
    	while(cin>>n){
    		for(int i=1;i<=n;i++){
    			cin>>a[i];
    		}
    		int l=1,r=1;
    		int sum = a[1];
    		for(int i=1,j=1;i<=n;i++){
    			f[i] = max(f[i-1],0) + a[i];
    			if(f[i-1] < 0){
    				j = i;
    			}
    			if(f[i] > sum){
    				sum = f[i];
    				l = j,r = i;
    			}
    		}
    		if(sum < 0){
    			cout<<"0 0 0"<<endl;
    		}
    		else{
    			cout<<sum<<' '<<l-1<<' '<<r-1<<endl;
    		}
    	}	
    	return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
  • 相关阅读:
    基于信号量与环形队列实现读写异步缓存队列
    数组反转(LeetCode)
    大容量中间继电器 RXMH2 RK223 067 DC110V JOSEF约瑟
    安卓讲课笔记1.1 搭建开发环境
    用帆软报表FineReport打造公司数字化经营报表
    QPIC阅读笔记
    新机Word/PowerPoint新建空白文档后闪退问题
    解密铭控传感从数字压力表到多品类物联感知硬件的发展史!
    LeetCode 619, 58, 24
    Nginx配置ssl证书实现https访问
  • 原文地址:https://blog.csdn.net/fatfairyyy/article/details/126697632