注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

求连续子序列最大和算法(经典的算法考试题和面试题)[稍微有点原创]  

2010-10-30 03:25:27|  分类: algorithms |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

这个问题在很多书上都是有的,算法本身比较简单,但是其内在的原理和思想没见过几个人细说的,在这里我稍微说一下,算是一点原创的想法吧。直观的想法就是我们把所有连续子序列和找出来,之后把其中最大的拿出就成了,可是这样做显然是不经济的。仔细思考一下问题就会发现这个问题本身有很强的特点。由于子串连续性,我们的最大子串的出现是有条件的,那么这条件是什么呢?考虑如下的子序列,

    

    

它的最大子序列是

    

而如果原子序列右端再加入一新的元素时,新的最大子序列只可能是或是从最新的右端向左数最大的连续子序列,因此我们要做的只是计录现在序列的最大子序列值和紧挨右端的最大子序列值,注意我们的子序列可以为空,因此哪果子序列的值为负,我们就可以把它丢弃,用0做最大子序列值。因此维护一个最大右端子序列值是十分容易的,如果它是负的就舍弃它,从下一个开始计数,如果是正就留着它,同时如果它比先前存储的原最大连续子序列值大的话就把最大值设为当前的最大连续最大右端子序列的值,这样只要一次遍历就可以把结果求出。下面是我实现的代码,仅供参考(注,如下代码使用到了C++0x里的新特性,如果你的编译器不支持可以换用支持0x的新编译器)。

 

//file FindGreatestSubArray

//written by saturnman

#include<iostream>

#include<utility>

#include<vector>

using namespace std;

typedef pair<int,int> start_length;

template<class T>

pair<start_length,T> FindTheGreatestSubArray(const vector<T>& input_arr)

{

    int start = 0;

    int length = 0;

    T max_array_sum = T();

    int current_array_index = 0;

    int current_array_length = 0;

    T current_array_sum = T();

 

    for(int i=0;i<input_arr.size();++i)

    {

        current_array_sum += input_arr[i];

        ++current_array_length;

        if(current_array_sum > max_array_sum)

        {

            max_array_sum = current_array_sum;

            start = current_array_index;

            length = current_array_length;

        }

        else if(current_array_sum <=0)

        {

            current_array_sum = 0;

            current_array_length = 0;

            current_array_index = i+1;

        }

    }

    return pair<start_length,T>(start_length(start,length),max_array_sum);

}

int main()

{

    vector<int> v = {2,-2,3,2,32,-5,-2,8,-3,11,-11,-3,5,-1};

    pair<start_length,int> res = FindTheGreatestSubArray(v);

    cout<<"max sum="<<res.second<<" from "<<res.first.first<<" to "<<res.first.first+res.first.second-1<<endl;

    return 0;

}

 

  评论这张
 
阅读(1409)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017