欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

连续和 博客分类: 练习题  

程序员文章站 2024-03-11 12:47:01
...

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

 

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

           第二步,对于最大和而言,所取的区间段一定在某个正数处结尾。可以用递归的方式求得第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++;
	}
}