连续和
问题：求一个数组的连续和的最大值
?
思路：第一步，将数组合并成正负交错的数组
? ? ? ? ? ?第二步，对于最大和而言，所取的区间段一定在某个正数处结尾。可以用递归的方式求得第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++;}}?