连续和 博客分类： 练习题

问题：求一个数组的连续和的最大值

 

思路：第一步，将数组合并成正负交错的数组

           第二步，对于最大和而言，所取的区间段一定在某个正数处结尾。可以用递归的方式求得第i处结尾的最大和与第i+2处结尾的最大和的关系。

 

源码：

#include <iostream>
using namespace std;

int revise(int *A, int n){
	int j=0;
	int k=0;
	for(int i=0;i<n;i++){
		if(i==n-1||A[i]*A[i+1]<0){
			int temp=0;
			for(int t=j;t<=i;t++){
				temp+=A[t];
			}
			A[k++]=temp;
			j=i+1;
		}
	}
	return k;
}

int calMax(int *A,int n){
	if(n==1) return A[0];
	int temp,i;
	if(A[0]>=0){
		temp=A[0];i=0;
	}else{
		temp=A[1];i=1;
	}
	int max=temp;
	while(i+2<n){
		temp=(temp+A[i+1]>0)?(temp+A[i+1]+A[i+2]):A[i+2];
		max=max>temp?max:temp;
		i+=2;
	}
	return max;
}


void main(){
	cout<<"输入（第一行输入测试组数，接下来每行第一个数输入数组大小，剩下为数据）："<<endl;
	int testNo;
	cin>>testNo;
	
	int *n=new int[testNo];
	int *result=new int[testNo];
	int i=0;

	int inputNo=testNo;
	while(inputNo--){     
		cin>>n[i];
		int *arr=new int[n[i]];
		for(int k=0;k<n[i];k++){
			cin>>arr[k];
		}
		int t=revise(arr,n[i]);
		result[i]=calMax(arr,t);
		i++;
	}
   
	i=0;
	cout<<"输出："<<endl;
	while(i<testNo){
		cout<<result[i]<<endl;
		i++;
	}
}