Posted on 2010-07-18 16:37
李熙建 阅读(790)
评论(0) 编辑 收藏 引用 所属分类:
算法
这个问题源于《编程之美》2.14 求数组的子数组之和的最大值扩展问题2
输出子数组的最大和同时输出子数组下标，时间复杂度为O(N)
源码：
#include <iostream>
using namespace std;
//startPos 最大和子数组的起始位置
//endPos 最大和子数组的结束位置
int MaxSum(int *A,int n,int &startPos,int &endPos)
{
int tmpStart = 0;
int nStart = A[0];
int nAll = A[0];
for (int i=1;i<n;i++)
{
if(nStart < 0)
{
nStart =0;
startPos = i;
}
nStart += A[i];
if (nStart>nAll)
{
nAll = nStart;
endPos =i;
tmpStart = startPos;
}
}
startPos = tmpStart;
return nAll;
}
int main()
{
int arr[11] = {-2,5,6,-6,4,-8,6,3,-1,2,-9};
int startP = 0,endP = 0;
int maxsubArrSumValue =0;
maxsubArrSumValue = MaxSum(arr,11,startP,endP);
cout<<maxsubArrSumValue<<endl<<startP+1<<endl<<endP+1<<endl;
system("pause");
return 0;
}