《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)
blank

相关推荐

  • 解决eclipse乱码问题[通俗易懂]

    解决eclipse乱码问题[通俗易懂]本文章主要解决eclipse工程区乱码问题。

  • 初探Protostuff的使用[通俗易懂]

    初探Protostuff的使用[通俗易懂]初探Protostuff的使用最近在学习RPC,看到了一个叫做Protostuff的库,是基于谷歌ProtocalBuffer的序列化库,之前了解过ProtocolBuffer,对学习了一些资料后,写了个demo,记录下来。什么是ProtocolBuffer?ProtocolBuffer是谷歌出品的一种数据交换格式,独立于语言和平台,类似于json。Google提供…

  • php代码执行函数_php代码如何运行

    php代码执行函数_php代码如何运行**php代码执行函数解析**​一、代码执行漏洞原理:用户输入的数据被当做后端代码进行执行<?php@eval($_REQUEST[8])?>//其实一句话木马的本质就是一个代码执行漏洞。用户输入的数据被当做代码进行执行。这里提一下RCE(remotecommand/codeexecute)远程命令或者代码执行。现在只要渗透的最终情况可以实现执行命令或者是代码都属于RCE,例如代码执行、文件包含、反序列化、命令执行,甚至是写文件Getshell都可以属于RCE在PHP存在诸多

  • phpstorm2021.3激活码 3月最新注册码

    phpstorm2021.3激活码 3月最新注册码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • Oracle 创建表空间

    Oracle 创建表空间–删除表空间droptablespacenacosincludingcontentsanddatafiles—-创建表空间并定义路径createtablespacenacos–表空间名datafile’D:/app/Administrator/oradata/nacos/nacos.dbf’size500m–大小初始值autoextendon–自动扩展next50mmaxsize20480m–每次扩展50m,最大为20480mex…

  • 阿里核心系统团队博客在哪_阿里云是谁创始人

    阿里核心系统团队博客在哪_阿里云是谁创始人http://csrd.aliapp.com/阿里核心系统团队博客基础极致分享Home招聘信息阿里核心系统团队介绍TFS运维平台改造1604天bylinqinginTFSTFS负责运维的同学在工作过程中,积累了各种运维脚本

发表回复

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

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