可以相应参考大神的解法http://blog.csdn.net/sgbfblog/article/details/8032464
这道题目虽然不难，但是找到一个简便的复杂度低一点算法还是挺难的，自己一开始写的程序太过繁琐，运行节点都没有问题，就是最后超时了！题目提交过程当中，出现了这么一个错误，reference to 'end' is ambiguous，这表示end与gcc编译器内部库函数变量重复了，MARK一下!
先给出原题
下面是我自己第一次写的代码，很容易想到，但由于for循环嵌套太多，算法太复杂，复杂度为N的三次方
#include <iostream>
#define mm 10001
using namespace std;
int main()
{
int M,arr[mm]={0};
int first=mm;
int last=mm;
int max=0;
cin>>M;
for(int i=1;i<=M;i++)
cin>>arr[i];
int k,j=1;
while(arr[j]<0&&j<=M)
j++;
if(j==M+1)
{
cout<<"0 "<<arr[1]<<" "<<arr[M];
return 0;
}
for(k=1;k<=M;k++)//第k次取出的序列包含k个数值
{
for(j=1;j<=M+1-k;j++)//每一次取出连续k个数相加，编号从j开始到j+k-1结束
{
int sum=0;
for(int i=j;i<=j+k-1;i++)
sum=sum+arr[i];//将取出来的连续数值序列相加
if(sum>max)
{
max=sum;
first=j;
last=j+k-1;
}
else if(sum==max)
{
if(first+last>j+j+k-1)
{
first=j;
last=j+k-1;
}
}
}
}
cout<<max<<" "<<arr[first]<<" "<<arr[last];
return 0;
}
下面参考了下别人自己又想了想，的确至少有一层fou循环是没有用的，可以把代码更改如下2.0版本，耗时56ms
#include <iostream>
#define mm 10001
using namespace std;
int main()
{
int M,arr[mm]={0};
int first=mm;
int last=mm;
int max=0;
cin>>M;
for(int i=1;i<=M;i++)
cin>>arr[i];
int k,j=1;
while(arr[j]<0&&j<=M)
j++;
if(j==M+1)
{
cout<<"0 "<<arr[1]<<" "<<arr[M];
return 0;
}
for(k=1;k<=M;k++)//第k次取出的序列包含k个数值
{
int sum=0;
for(j=k;j<=M;j++)//每一次取出连续k个数相加，编号从j开始到j+k-1结束
{
sum=sum+arr[j];
if(sum>max)
{
max=sum;
first=k;
last=j;
}
else if(sum==max)
{
if(first+last>j+k)
{
first=j;
last=j;
}
}
}
}
cout<<max<<" "<<arr[first]<<" "<<arr[last];
return 0;
}
下面有参考别人代码，运用动态规划思想，算法继续简化，于是有了终极3.0版本，耗时只有3ms
#include <iostream>
#define mm 10001
using namespace std;
int maxsequence3(int a[], int len);
int start=0;
int last=0;
int main()
{
int M,arr[mm]={0};
int max=0;
cin>>M;
for(int i=0;i<M;i++)
cin>>arr[i];
int j=0;
while(arr[j]<0&&j<M)
j++;
if(j==M)
{
cout<<"0 "<<arr[0]<<" "<<arr[M-1];
return 0;
}
int sum=maxsequence3(arr, M);
cout<<sum<<' '<<arr[start]<<' '<<arr[last];
return 0;
}
int maxsequence3(int a[], int len)
{
int maxsum, maxhere,temp_start,temp_last;
temp_start=0;
temp_last=0;
maxsum=a[0];
maxhere=a[0]; //初始化最大和为a【0】
for (int i=1;i<len;i++)
{
if (maxhere<= 0)
{
maxhere=a[i]; //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]
temp_start=i;
}
else
{
maxhere+=a[i]; //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和
temp_last=i;
}
if (maxhere>maxsum)
{
maxsum=maxhere; //更新最大连续子序列和
start=temp_start;
last=temp_last;
}
}
if(start>last)
last=start;//避免出现下面状况start不断更新，而last保持第一个不变，所以额外添加这个if判断语句，如果输入序列为 -1 -2 -3 0 -4，这个if判断就是必须的
return maxsum;
}
不得不承认一个优质算法带来运算时间会减少很多！