Posted on 2010-07-18 16:37
李熙建 閱讀(814)
評論(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;
}