概要
题目描述 给定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 输出
20 11 13 10 1 4 10 3 5 10 10 10 0 -1 -2 0 0 0
思路
best,best_tmp分别存储最大和和当前的连续序列和 bestL,bestL_tmp分别存储左边第一个和当前的连续序列左边第一个 bestR,bestR_tmp分别存储最后一个和和当前的连续序列最后一个 best小于0时把重新best，bestL，bestR置换当前数字。否则则best进行累加，bestR替换为当前数字
AC代码
#include <iostream>
#include <cstring>
using namespace std;
long long data[
10000];
int K;
long long best,best_tmp;
long long bestL,bestL_tmp;
long long bestR,bestR_tmp;
int main()
{
while(
cin>>K){
if(K ==
0){
break;
}
memset(data,
0,
sizeof(data));
for(
int i =
0 ; i < K ; i++){
cin>>data[i];
}
best = bestL = bestR = data[
0];
best_tmp = bestL_tmp = bestR_tmp = data[
0];
for(
int i =
1 ; i < K ; i++){
if(best_tmp <
0){
best_tmp = bestL_tmp = bestR_tmp = data[i];
}
else{
best_tmp += data[i];
bestR_tmp = data[i];
}
if(best < best_tmp){
best = best_tmp;
bestL = bestL_tmp;
bestR = bestR_tmp;
}
}
if(bestR == bestR_tmp && bestL == bestL_tmp && best <
0){
best =
0;
bestR = data[K-
1];
bestL = data[
0];
}
cout<<best<<
" "<<bestL<<
" "<<bestR<<endl;
}
return 0;
}
