笔试题5——最大连续子数列

题目描述:
给出一个数列(元素个数不多于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;
}
上一篇:C++ STL——常用算法


下一篇:581. Shortest Unsorted Continuous Subarray