机试:最大子序列的和

问题描述:

算法思想:
若第(i-1)个序列的小于0,则第i个序列的最大值为nums[i];
若第(i-1)个序列的小于0,则第i个序列的最大值为max(i-1) + nums[i];

如果max(i-1)>0,max(i)=max(i-1)+Nums(i)
如果max(i-1)<=0,max(i)=Nums(i)
1
2

代码示例:

#include 
//该算法默认最大序列和大于0 

using namespace std;
int main(){
	int n;
	cout << "输入序列长度" << endl; 
	cin >> n;
//	输入序列 
	cout << "输入序列" << endl; 
	int nums[n+1];
	for(int i = 1; i <= n; i++){
		cin >> nums[i];
	}
	
//	存放可能的最大子序列和的结果 
	int max[n+1];
	max[0] = 0;
	
//	记录各个可能的最大子序列和的结果 
	for(int i = 1; i < n; i++){
		if(max[i-1] > 0){
			max[i] = max[i-1] + nums[i];  
		}else{
			max[i] = nums[i];
		}
	}
	int max_sum = max[0];
	int rtag,ltag; //记录最大序列和的首尾位置 
//	对子序列和的结果进行筛选 
	for(int i = 1; i < n; i++){
		if(max[i] > max_sum){
			rtag = i;
			max_sum = max[i];
		}
	}
//	循环遍历找到首位置 
	for(int i = rtag; i > 0; i--){
		if(max[i] < 0){
			ltag = i + 1;
		}
	}
	cout << "输出样例" << endl; 
	cout << max_sum <<" " << ltag << " " << rtag << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47