About

• The max subsequence sum

Code

• 假设0是最小的值

SubsequenceSum

• beg 开始迭代器

• end 结束迭代器

• value 和

• 子序列之和

::value_type>
struct SubsequenceSum {
    It beg,end;
    T  value;
SubsequenceSum()
    :beg(),end(),value()
{}

SubsequenceSum(const It& b,const It& e,const T& v)
    :beg(b),end(e),value(v)
{}

template <typename O>
bool operator > (const SubsequenceSum<O>&amp; o) const
{
    return this->value > o.value;
}

template <typename O>
bool operator <  (const SubsequenceSum<O>&amp; o) const
{
    return !(o > *this);
}
};
//输出需要原始begin迭代器

template <typename It,typename T = typename std::iterator_traits::value_type>

void printr(const SubsequenceSum& ss,It beg)

{

std::cout <<" [beg:"<<(ss.beg - beg)<<" end:"<<(ss.end - beg)<<" -> "<<ss.value<<" ]n";

}

ON3

• 复杂度 O(N3)

::value_type>
    SubsequenceSum maxSubsequenceSum_ON3(It beg,It end)
{
    // assume zero is the minimum value
    // [end - end] means not found
    SubsequenceSum cur,max(end,end,0);
for (It i = beg;i < end;i ++) {
    for (It j = i;j < end;j ++) {
        cur = SubsequenceSum<It>(i,j,0);
        // generate [i - j]'s sum
        for (It k = i;k <= j;k ++) {
            cur.end   =  k;
            cur.value += *k;
        }
        if (cur > max) {
            max = cur;
        }
    }
}

return max;
}

ON2

• 复杂度 O(N2)

::value_type>
    SubsequenceSum maxSubsequenceSum_ON2(It beg,It end)
{
    SubsequenceSum cur,0);
for (It i = beg;i < end;i ++) {
    cur = SubsequenceSum<It>(i,i,0);
    // generate [i - j]'s sum
    for (It j = i;j < end;j ++) {
        cur.end   =  j;
        cur.value += *j;           
        if (cur > max) {
            max = cur;
        }
    }
}

return max;
}

ON

• 复杂度 O(N)

::value_type>
    SubsequenceSum maxSubsequenceSum_ON1(It beg,It end)
{
    SubsequenceSum cur(beg,beg,0),0);
for (It i = beg;i < end;i ++) {     
    //add [i - j]'s sum
    cur.end   =  i;
    cur.value += *i;
    if (cur > max) {
        max = cur;
    } else if (cur.value < 0) {
        cur = SubsequenceSum<It>(i + 1,i + 1,0);
    }
}

return max;
}

main

#include 
#include 
int main()

{

int array[] = {6,-20,3,-6,8,-19,-1,-5,7,1,-10,15,-23};   
printr(maxSubsequenceSum_ON3(array,array + sizeof(array) / sizeof(int)),array);
printr(maxSubsequenceSum_ON2(array,array);
printr(maxSubsequenceSum_ON1(array,array);

return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!