最大连续子序列
中南 - 最大连续子序列
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
给定 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( <100000) ，第 2 行给出 K 个整数，每个整数的范围-10000至10000 ，中间用空格分隔。
输出描述:
对每个测试用例， 在 1 行里输出最大和、 最大连续子序列的第一个和最后一个元素的下标，中间用空格分隔。 如果最大连续子序列不唯一， 则输出序号 i 和 j 最小的那个（如输入样例的第 2、3组）。若所有 K 个元素都是负数，则定义其最大和为0，输出"0 0 0"。
输入输出样例
输入样例#:
复制
8 6 -2 11 -4 13 -5 -2 10 20 -10 1 2 3 4 -5 -23 3 7 -21 6 5 -8 3 2 5 0 1 10 3 8 -1 -5 -2 3 -1 0 -2 0 4 -1 -2 -4 -3
输出样例#:
复制
27 0 7 27 10 19 3 3 3 0 0 0
题目来源
中南大学机试题
#include<bits/stdc++.h> using namespace std; #define N 1000005 int dp[N] = {0}; int v[N] = {0}; int t[N] = {0}; int s[N] = {0}; int main(){ int n; while(cin>>n){ bool negative = true; for(int i = 0; i < n; i ++){ cin>>s[i]; if(s[i] > 0){ negative = false; } } int temp = 0; int m = s[0], sum = s[0]; int start, end; //从这个temp开始依次往后累加， 如果>0我们就一直累加， //并且每次每次累加完都判断一次是否超过了历史最大值 //超过了更新他 for(int i = 1; i < n; i ++){ if(m < 0){//前面的和<0 m = s[i]; temp = i; } else{ m = m + s[i];//累加 } if(m > sum){//和>0时我们就一直判断 sum = m; start = temp; end = i; } }// if(!negative){ cout<<sum<<" "<<start<<" "<<end<<endl; } else { cout<<"0 0 0"<<endl; } } // }最大连续子序列
已解决
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
给定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，输出整个序列的首尾元素。
输入输出样例
输入样例#:
复制
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
输出样例#:
复制
20 11 13 10 1 4 10 3 5 10 10 10 0 -1 -2 0 0 0
题目来源
浙江大学/中国矿业大学/暨南大学机试题
#include<bits/stdc++.h> using namespace std; //1. 全局大数组，防栈溢出 const int MAXN = 1000005; long long s[MAXN]; long long dp[MAXN]; int main() { int k; while(cin >> k){ if(k == 0){ break; } bool negative = true; for(int i = 0; i < k; i ++){ cin>>s[i]; if(s[i] >= 0){ negative = false; } } // for(int i = 0; i < k; i ++){ // cout<<s[i]<<" "; // } // cout<<endl; int start = 0, end = 0;//记录最大的 int temp = 0;//记录临时的起点 注意初始化！！！！ int sum = s[0], m = s[0]; for(int i = 1; i < k; i ++){ if(m < 0){//小于0就从i这里重新开始 m = s[i]; temp = i; } else{//大于0就一直累加 m = m + s[i]; } if(m > sum){//当前的最大值超过之前的那个了 sum = m; start = temp; end = i; } } if(negative){ cout<<"0"<<" "<<s[0]<<" "<<s[k - 1]<<endl; } else{ cout<<sum<<" "<<s[start]<<" "<<s[end]<<endl; } } }复旦-最大连续子序列
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
给定一个数字序列A1,A2…An，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大，输出这个最大和。
输入输出格式
输入描述:
第一行输入一个整数n，表示数列大小 第二行输入n个整数
输出描述:
输出一个整数，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大
输入输出样例
输入样例#:
复制
6 -2 11 -4 13 -5 -2
输出样例#:
复制
20
题目来源
复旦大学机试
#include<bits/stdc++.h> using namespace std; int dp[10005]; int dp1[10005]; int dp2[10005]; int v[10005]; int s[10005]; int t[10005]; int pre[10005]; int main(){ int n, w; while(cin>>n){ for(int i = 0; i < n; i ++){ cin>>s[i]; } int m = s[0], sum = s[0]; for(int i = 1; i < n; i ++){ // cout<<s[i]<<" "<<m<<" "<<sum<<endl;; // dp[i] = max(s[i], dp[i - 1] + s[i]); if(m < 0){ m = s[i]; } else{ m = m + s[i]; } if(m > sum){ sum = m; } } cout<<sum<<endl; } }