#include<iostream>
using namespace std;
/************************************************************************/
/*面6有一个数组a[n],里面的数只有两种：-1或1。
i，j是两个整数，假设0<=i<=j<=n-1，找出a[i]到a[j]中连续数之和最大的部分（如果最大部分存在相等的则优先找最短的）。
*/
/************************************************************************/
#include <iostream>
using namespace std;
typedef struct node
{
int begin;
int end;
}Node;
void Find(int number[], int length)
{
if(length == 0)//如果数组为空直接返回
return;
int Max = number[0], Acclulate = number[0];//初始化最大值为数组的第一个值
Node *Position = new Node[length];//用于存取到当前位置可能的最大值
Node MaxPosition = {0, 0};//初始化最大的起始位置和终止位置
Position[0].begin = 0;
Position[0].end = 0;
for(int i = 1; i < length; i++)
{
if(Acclulate > 0)//前面的累积和大于零时，起始位置固定，而终止位置每次都往后移动一个位置
{
Position[i].begin = Position[i - 1].begin;//起始位置固定,只需取前一个节点的值.begin即可
Position[i].end = Position[i - 1].end + 1;//终止位置每次都往后移动一个位置:前一个节点的值.end+1
Acclulate += number[i];//此时判断number[i]有效，计入 累积和Acclulate中
if(Acclulate > Max)//如果 重新计算后的 累积和Acclulate大于 Max
{
Max = Acclulate;
MaxPosition = Position[i];//重新定位 最大的起始位置和终止位置
}
// cout<<"前面的累积和大于=>>";
// cout<<"起点number["<<MaxPosition.begin<<"]="<<number[MaxPosition.begin]
// <<",终点number["<<MaxPosition.end<<"]="<<number[MaxPosition.end]<<endl;
}
else//前面的累加和小于等于 零， 则重新设定起始位置和终止位置
{
Position[i].begin = i;
Position[i].end = i;
Acclulate = number[i];
if(number[i] > Max)//如果当前number[i]大于Max，则重新设定起始位置和终止位置，否则保持不变
{
Max = number[i];
MaxPosition = Position[i];
}
// cout<<"累加和小于等于=>>";
// cout<<"起点number["<<MaxPosition.begin<<"]="<<number[MaxPosition.begin]
// <<",终点number["<<MaxPosition.end<<"]="<<number[MaxPosition.end]<<endl;
}
}
cout <<endl<< "最大的值为：" << Max << endl;
cout <<"起点number["<<MaxPosition.begin<<"]="<<number[MaxPosition.begin]
<<",终点number["<<MaxPosition.end<<"]="<<number[MaxPosition.end]<<endl;
cout << "他们分别为：";
for( i = MaxPosition.begin; i <= MaxPosition.end; i++)
cout << number[i] <<" ";
cout << endl;
delete [] Position;
}
int main(void)
{
/************************************************************************/
/*最大的值为：5
起点 number[0]=3,终点number[8]=1
他们分别为：3 -1 -1 1 1 -1 1 11
*/
/************************************************************************/
// inta[10]={3,-1,-1,1,1,-1,1,1,1,-1};//总数是从0到9
/************************************************************************/
/* 最大的值为：4
起点number[3]=1,终点 number[8]=1
他们分别为：1 1 -1 11 1
*/
/************************************************************************/
//inta[10]={2,-1,-1,1,1,-1,1,1,1,-1};//总数是从0到9
/************************************************************************/
/*最大的值为：3
起点 number[0]=3,终点number[0]=3
他们分别为：3
*/
/************************************************************************/
//inta[10]={3,-1,-1,-1,1,-1,1,1,1,-1};//总数是从0到9
/************************************************************************/
/*最大的值为：3
起点 number[6]=1,终点number[8]=1
他们分别为：1 1 1
*/
/************************************************************************/
//inta[10]={2,-1,-1,-1,1,-1,1,1,1,-1};//总数是从0到9
/************************************************************************/
/*
最大的值为：-1
起点 number[1]=-1,终点 number[1]=-1
他们分别为：-1
Press any key to continue
*/
/************************************************************************/
int a[10]={-2,-1,-1,-1,-1,-1,-1,-1,-1,-1};//总数是从0到9
Find(a, 10);
return 0;
}
联系客服
