跨域 Java程序员 awk cmake nlp angular material react脚手架 jquery遍历对象 jquery关闭当前窗口 android调试工具 matlab生成对角矩阵 idea全文搜索快捷键 mysql将时间戳转换成日期 python实例 python数据库 mysql建表 mysql连接 python中sort函数 python环境设置 python变量类型 java最新框架 java如何连接mysql java集合转数组 java命令 java中map java方法调用 java运行 java当前日期 php实例代码 图吧导航怎么样 pyh raid0教程 maya2008 服务器系统安装 程序卸载 hzfs 氤氲之息哪里爆率高 主播音效 分割字符串 脚本文件
当前位置: 首页 > 学习教程  > 编程语言

最大字段和问题

2020/10/8 20:06:16 文章标签:

最大子段和问题: 给定由n个整数(可能有负整数)组成的序列(a1,a2,,an),最大子段和要求该序列形如(∑kijak)\displaystyle ( \sum_{ki}^j a_k )(ki∑j​ak​)的最大值(1≤\…

最大子段和问题:
给定由n个整数(可能有负整数)组成的序列(a1,a2,···,an),最大子段和要求该序列形如 ( ∑ k = i j a k ) \displaystyle ( \sum_{k=i}^j a_k ) (k=ijak)的最大值(1 ≤ \displaystyle\leq i ≤ \displaystyle\leq j ≤ \displaystyle\leq n)。例如,序列(-20,11,-4,13,-5,-2)的最大子段和为 ( ∑ k = 2 4 a k ) \displaystyle ( \sum_{k=2}^4 a_k ) (k=24ak)=20。

#include<iostream>
using namespace std;

int MaxSum(int a[],int left,int right)
{
    int sum=0,midSum=0,leftSum=0,rightSum=0;
    int center,s1,s2,lefts,rights;
    if(left==right)
        sum=a[left];
    else{
        center=(left+right)/2;
        leftSum=MaxSum(a,left,center);
        rightSum=MaxSum(a,center+1,right);
        s1=0;lefts=0;
        for(int i=center;i>=left;i--)
        {
            lefts+=a[i];
            if(lefts>s1)
                s1=lefts;
        }
        s2=0;
        rights=0;
        for(int j=center+1;j<=right;j++)
        {
            rights+=a[j];
            if(rights>s2)
                s2=rights;
        }
        midSum=s1+s2;
        if(midSum<leftSum)
            sum=leftSum;
        else
            sum=midSum;
        if(sum<rightSum)
            sum=rightSum;
    }
    return sum;
}

int main()
{
    int a[1000];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cout<<MaxSum(a,0,n-1);

}

本文链接: http://www.dtmao.cc/news_show_250195.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?