是技术,更是艺术

一心编程,就没有解决不了的问题
posts - 9, comments - 11, trackbacks - 0, articles - 0

求数组子数组之和的最大值和子数组位置

Posted on 2010-07-18 16:37 李熙建 阅读(723) 评论(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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理