Dain

写出一个可以工作的程序并不够

统计

留言簿(3)

积分与排名

良师益友

阅读排行榜

评论排行榜

最大的子序列和问题

求解该问题的四种算法：
 时间O(N3)，算法一
int  MaxSubsequenceSum( const   int  A[], int  N)
 {
     int  ThisSum,MaxSum,i,j,k;
    
    MaxSum  =   0 ;
     for (i  =   0 ;i  <  N;i ++ )
         for (j  =  i;j  <  N;j ++ )
         {
            ThisSum  =   0 ;
             for (k  =  i;k  <=  j;k ++ )    ThisSum  +=  A[k];                
             if (ThisSum  >  MaxSum)    MaxSum  =  ThisSum;
        }
        
     return  MaxSum;
}
时间O(N2)，算法二
int  MaxSubsequenceSum( const   int  A[], int  N)
 {
     int  ThisSum,MaxSum,i,j;
    
    MaxSum  =   0 ;
     for (i  =   0 ;i  <  N;i ++ )
     {
        ThisSum  =   0 ;
         for (j  =  i;j  <  N;j ++ )
         {
            ThisSum  +=  A[k];                
             if (ThisSum  >  MaxSum)    MaxSum  =  ThisSum;
        }
    }
        
     return  MaxSum;
}
时间O(NlogN)，算法三
static   int  MaxSubSum( const   int  A[], int  Left, int  Right)
 {
     int  MaxLeftSum,MaxRightSum;
     int  MaxLeftBorderSum,MaxRightBorderSum;
     int  LeftBorderSum,RightBorderSum;
     int  Center,i;
    
     if (Left  ==  Right)
         if (A[left]  >   0 )     return  A[left];
         else      return   0 ;
            
    Center  =  (Left  +  Right)  /   2 ;
    MaxLeftSum  =  MaxSubSum(A,Left,Center);
    MaxRightSum  =  MaxSubSum(A,Center  +   1 ,Right);
    
    MaxLeftBorderSum  =   0 ;
    LeftBorderSum  =   0 ;
     for (i  =  Center;i  >=  Left;i -- )
     {
        LeftBorderSum  +=  A[i];
         if (LeftBorderSum  >  MaxLeftBorderSum)    MaxLeftBorderSum  =  LeftBorderSum;
    }
    
    MaxRightBorderSum  =   0 ;
    RightBorderSum  =   0 ;
     for (i  =  Center  +   1 ;i  <=  Right;i ++ )
     {
        RightBorderSum  +=  A[i];
         if (RightBorderSum  >  MaxRightBorderSum)    MaxRightBorderSum  =  RightBorderSum;
    }
    
     return  Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum  +  MaxRightBorderSum);
}

int  MaxSubsequenceSum( const int  A[],int  N)
 {
     return  MaxSubSum(A, 0 ,N  -   1 );    
}
时间O(N)，算法四
intMaxSubsequenceSum( const int  A[], int  N)
 {
     int  ThisSum,MaxSum,i;
    
    ThisSum  =  MaxSum  =   0 ;
     for (i  =   0 ;i  <  N;i ++ )
     {
        ThisSum  +=  A[i];
         if (ThisSum  >  MaxSum)
            MaxSum  =  ThisSum;
         else
            ThisSum  =   0 ;
    }
    
     return  MaxSum;
}


参考《数据结构与算法分析》

posted on 2007-02-07 10:52 Dain 阅读(1039) 评论(7)  编辑 收藏 引用 所属分类: 算法 、笔记

评论

# re: 最大的子序列和问题[未登录] 2007-02-08 01:36 豪

呵呵， dp是王道  回复  更多评论   

# re: 最大的子序列和问题 2007-02-08 16:53 Dain

嗯，dp
对于这个问题，算法三和四都是不错的思路@豪
  回复  更多评论   

# re: 最大的子序列和问题 2007-02-09 16:24 alai04

楼主开什么玩笑,算法四明显是不对的嘛,是考一下我们的眼力吗?  回复  更多评论   

# re: 最大的子序列和问题 2007-03-25 20:50 felix

四不对
如：
1 5 -3 2 4
  回复  更多评论   

# re: 最大的子序列和问题 2007-03-25 20:51 felix

三用的是分治，不是DP吧？  回复  更多评论   

# re: 最大的子序列和问题 2007-03-30 11:12 dqchen

第四个
MaxSum = -((static_cast<unsigned int>(~0)) >> 1) - 1;

ThisSum = 0;
for (int i = 0;i < A.size();i++)
{
ThisSum += A[i];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
else
ThisSum = 0;
}
  回复  更多评论   

# 第四个算法的实现是错误的 2008-07-04 17:53 wetwoo

输入如下：-2 11 -4 13 -5 -2
输出如下：13
正确输出应该为：20
修改如下：
intMaxSubsequenceSum( const int A[], int N)
{
int ThisSum,MaxSum,i;

ThisSum = MaxSum = 0 ;
for (i = 0 ;i < N;i ++ )
{
ThisSum += A[i];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
else if(ThisSum < 0)
ThisSum = 0 ;
}

return MaxSum;
}   回复  更多评论   


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