《github一天一道算法题》:分治法求数组最大连续子序列和「建议收藏」

《github一天一道算法题》:分治法求数组最大连续子序列和

大家好,又见面了,我是全栈君。

看书、思考、写代码。

/***************************************
 * copyright@hustyangju 
 * blog: http://blog.csdn.net/hustyangju 
 * 题目:分治法求数组最大连续子序列和
 * 思路:分解成子问题+合并答案
 * 时间复杂度:O(n lgn)
 * 空间复杂度:O(1) 
***************************************/
#include <iostream>

using namespace std;

template<class type>
class max_subarray
{
public:
    max_subarray(type *p):_p(p){}
    ~max_subarray(){}
    type max_aside_subarray(int s,int e);
protected:
    type max_cross_subarray(int s,int m,int e);
    type _max(type a,type b,type c);
private:
    type *_p;
};

template<class type>
type max_subarray<type>::_max(type a, type b, type c)
{
    if((a>=b)&&(a>=c))
        return a;
    else if((b>=a)&&(b>=c))
        return b;
    else
        return c;
}

template<class type>
type max_subarray<type>::max_cross_subarray(int s, int m, int e)
{
    type left_sum=*(_p+m);
    type right_sum=*(_p+m+1);
    for(int i=m;i>=s;i--)
    {
        type sum=0;
        sum+=*(_p+i);
        if(sum>left_sum)
            left_sum=sum;
    }//for
    for(int i=m+1;i<=e;i++)
    {
        type sum=0;
        sum+=*(_p+i);
        if(sum>right_sum)
            right_sum=sum;
    }//for
    return(left_sum+right_sum);
}

template<class type>
type max_subarray<type>::max_aside_subarray(int s, int e)
{
    int m=0;
    type left_sum,right_sum,cross_sum;
    if(s==e)
        return(*(_p+s));
    else
        m=int((s+e)/2);
    left_sum=max_aside_subarray(s,m);
    cross_sum=max_cross_subarray(s,m,e);
    right_sum=max_aside_subarray(m+1,e);
    return _max(left_sum,cross_sum,right_sum);
}

int main()
{
            int array1[10]={1,-2,-3,4,5,6,-7,-8,9,10};
           // float array2[10]={1.0,-2.0,-3.0,4.0,5.2,6.0,-7.0,-8.0,9.0,-10.0};
            max_subarray<int> mysubarray1(array1);
            //max_subarray<float>mysubarray2(array2);
            cout<<"max sum of sub array is: ";
            cout<<mysubarray1.max_aside_subarray(0,9)<<endl;
           // cout<<"max sum of sub array is: ";
            //cout<<mysubarray2.max_aside_subarray(0,9)<<endl;
}


《github一天一道算法题》:分治法求数组最大连续子序列和「建议收藏」

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115874.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 关于大数据平台,这有一套完整的方法论,你确定不收藏?[通俗易懂]

    关于大数据平台,这有一套完整的方法论,你确定不收藏?[通俗易懂]大数据时代这个词被提出已有10年了吧,越来越多的企业已经完成了大数据平台的搭建。随着移动互联网和物联网的爆发,大数据价值在越来越多的场景中被挖掘,随着大家都在使用欧冠大数据,大数据平台的搭建门槛也越来越低。借助开源的力量,任何有基础研发能力的组织完全可以搭建自己的大数据平台。但是对于没有了解过大数据平台、数据仓库、数据挖掘概念的同学可能还是无法顺利完成搭建,因为你会发现太多的东西,和架构,你不知道如何去选择。今天给大家分享下大数据平台是怎么玩的。架构总览通常大数据平台的架构如上,从.

  • 年薪500万大数据工程师:讲解大数据建模方法和经验

    年薪500万大数据工程师:讲解大数据建模方法和经验大数据前言:建模的过程和方法是不断发展和完善的。可以说,不同的数据类型、不同的业务场景和不同的需求将有不同的建模方法。我同意他们的观点。但我想说的是,无论您的数据是什么,在大数据中构建自己的数据模型是很正常的。1。数据准备两。开展探索性数据分析三。初始模型的建立四。模型迭代构造分享大数据学习交流群:722680258零基础中高级视频资料,欢迎加入不定期分享资源数据准备:在大数据计算中没有太多的数据…

  • 机房建设效果图制作|机房鸟瞰图设计|教程文章

    机房建设效果图制作|机房鸟瞰图设计|教程文章因为时间关系,这里只做简易分析,如图所示案例,首先客户得提供资料,例如CAD布置图或是手绘图纸等。这是第一步。接下来,就需要根据资料和客户沟通,什么地方是什么东西东西,有什么需要特别注意的地方吗,地面,墙面等是什么材质。剩下的基本就是建模和渲染了。建模的时候要注意,一定要注意房间的高度,因为将来还有吊顶等。一般而言,内部房间的地面材质都是防静电地板,而墙面基本就是刷白或是吸音板铝塑板之类。

  • protel99se精彩教程[通俗易懂]

    protel99se精彩教程[通俗易懂]网上盛行的那个protel99se精彩教程中,PCB通用封装在哪?

  • document对象(DOM)–认识DOM

    document对象(DOM)–认识DOMdocument对象(DOM)–认识DOM文档对象模型DOM(DocumentObjectModel)定义访问和处理HTML文档的标准方法。DOM将HTML文档呈现为带有元素、属性和文本的树结构(节点树)。HTML文档可以说由节点构成的集合,DOM节点有:1.元素节点:<html>、<body>、<p>等都是元素节点,即标签。2.文本节…

  • 主流自动化运维工具支持的功能(运维自动化工具排行)

    主流的自动化运维工具有3种:Puppet、Saltstack和Ansible,用的最多的还是Ansible。Puppet:官网:www.puppetlabs.com,基于rubby开发,C/S架构,支持多平台,可管理配置文件、用户、cron任务、软件包、系统服务等。分为社区版(免费)和企业版(收费),企业版支持图形化配置。Saltstack:官网:https://saltsta…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号