题目描述:
给出一个数列(元素个数不多于100),数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列,使得这个子数列中包含的所有元素之和最大,在和最大的前提下还要求该子数列包含的元素个数最多,并输出这个最大和以及该连续子数列中元素的个数。
核心代码:
#include <iostream>
using namespace std;
int main()
{
int a[101];
int n, i, ans, len, tmp, beg;
cout << "请输入数列个数:";
cin >> n;
cout << "请输入各元素:" << endl;
for(int i = 1; i <= n; i++)
cin >> a[i];
cout << "您输入的数列为:" << endl;
for(int i = 1; i <= n; i++){
if(i < n)
cout << a[i] << " ";
else
cout << a[i] << endl;
}
tmp = 0;
ans = 0; //子数列的和
len = 0; //子数列的长度
beg = 0; //子数列起始位
for(i = 1; i <= n; i++){ //遍历以第i个元素开头的数列
if(tmp + a[i] > ans){ //新的子数列大于当前最大子数列
ans = tmp + a[i];
len = i - beg;
}
else if(tmp + a[i] == ans && i - beg > len){ //新的子数列等于当前最大子数列,并且个数大于上一最大子数列个数
len = i - beg;
}
if(tmp + a[i] < 0){ //新的子数列小于0,该数列重置0
beg = i;
tmp = 0;
}
else
tmp += a[i]; // 0<新的子数列<当前最大数列,存放入tmp中,以供下一轮加上新元素再与当前最大数列比较
}
cout << "最大和为: " << ans << endl;
cout << "该子数列连续个数为:" << len << endl;
return 0;
}