首页 > 试题广场 >

最大连续子序列

[编程题]最大连续子序列

热度指数：10949 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。

输入描述:

    测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( K< 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。

输出描述:

    对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。

示例1

输入

6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0

输出

算法知识视频讲解

Widdit

发表于 2022-03-01 13:14:48

假设大家都已经写过这道题的原题——最大连续子序列和，我们知道递推方程为 dp[i] = max(nums[i], dp[i - 1] + nums[i])。若 dp[i] = nums[i]，说明新起了一段序列；若 dp[i] = dp[i - 1] + nu 展开全文

健康快乐最重要

发表于 2020-02-25 20:56:05

思路用dp[i]，记录以i为末尾元素的子序列和。相对于之前的，只要增加end去记录最大子序列和的最后一个元素位置就可以，end确定后，从end往前找到一个小于0的位置，然后再+1，就是子序列开始，也就是begin的位置。 #include<iostream> #include< 展开全文

在考古的小鱼干很有气魄

发表于 2023-03-09 11:17:32

#include <bits/stdc++.h> using namespace std; int main(){ int n,tmp; vector<int> dp,data; while(cin>>n){ if(n == 0) break; 展开全文

犹豫的王者G了

发表于 2023-03-03 13:23:58

while True: try: k=int(input())#接收收入的整数K if k==0: break #若K=0，中止运算 list1=input().split() #接收K个整数，并存储到列表里展开全文

philos

发表于 2021-03-10 18:35:33

思路动态规划题目，我们用 dp[i] 表示以 nums[i] 结尾的连续子序列的最大元素和，则： dp[i] < 0，dp[i + 1] = nums[i + 1] dp[i] > 0，dp[i + 1] = dp[i] + nums[i + 1] 因为要输出首尾元素，其中尾部元素展开全文

Huster水仙

发表于 2023-02-09 22:47:05

简单DP 思路：统计以s[i]结尾的最大子序列和ans[i],多递推一个起始下标即可 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int 展开全文

牛客568792594号

发表于 2024-03-11 17:18:06

#include <bits/stdc++.h> using namespace std; const int N = 10010; int a[N]; int main(){ int k; while (cin >> k){ if (k == 0) con 展开全文

求求offer的土拨鼠很无聊

发表于 2023-03-11 15:12:39

#include <algorithm> #include <iostream> using namespace std; int main() { int k; while(cin>>k && k!=0){ int b[k]; 展开全文

21岁扶墙编程

发表于 2023-03-05 16:34:14

#include <iostream> #include <cstring> #include <iostream> #include<climits> using namespace std; const int maxn = 10001; cons 展开全文

刘思萌lsm

发表于 2024-02-06 12:50:40

#include <iostream> using namespace std; const int MAXN = 1e4+10; int arr[MAXN]; int answer[MAXN]; int Fun(int n){ int index; //最大值下标 i 展开全文

问题信息

动态规划数组

难度：

103条回答 145收藏 18006浏览

通过挑战的用户

查看代码

CITYHUA

2023-03-10 11:52:53
牛客49234...

2023-03-06 16:34:56
dumbbell

2023-03-05 16:23:16
郁闷的小白在收藏面经

2023-03-05 11:44:25
Koyang

2023-03-03 17:17:51

最大连续子序列

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题