当前位置: 首页 > news >正文

建设厅网站怎样刷身份证推广普通话的宣传内容

建设厅网站怎样刷身份证,推广普通话的宣传内容,国家示范建设成果网站,日照网站建设网站优化文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴线性DP一、题目 1、原题链接 1051. 最大的和 2、题目描述 对于给定的整数序列 A{a1,a2,…,an},找出两个不重合连续子段,使得两子段中所有数字的和最…

文章目录

  • 一、题目
    • 1、原题链接
    • 2、题目描述
  • 二、解题报告
    • 1、思路分析
    • 2、时间复杂度
    • 3、代码详解
  • 三、知识风暴
  • 线性DP

一、题目

1、原题链接

1051. 最大的和

2、题目描述

对于给定的整数序列 A={a1,a2,…,an},找出两个不重合连续子段,使得两子段中所有数字的和最大。

我们如下定义函数 d(A):在这里插入图片描述

我们的目标就是求出 d(A)

输入格式

第一行是一个整数 T,代表一共有多少组数据。

接下来是 T 组数据。

每组数据的第一行是一个整数,代表数据个数据 n,第二行是 n 个整数 a1,a2,…,an。

输出格式

每组数据输出一个整数,占一行,就是 d(A) 的值。

数据范围

1≤T≤30,2≤n≤50000,|ai|≤10000

输入样例

1
10
1 -1 2 2 3 -3 4 -4 5 -5

输出样例

13

样例解释
在样例中,我们取{2,2,3,-3,4}和{5}两个子段,即可>得到答案。

二、解题报告

1、思路分析

思路来源:y总讲解视频
y总yyds

(1)利用求单段连续子段和的方法,将所有子段和处理出来。
(2)单段连续子段和最大求解方法:

  • dp[i]表示以a[i]结尾的所有连续子段和的最大值。
  • 可以将dp[i]分为两部分:①只包含a[i]②不仅包含a[i]还包含a[i]之前的某些数。
  • 可知这两部分和分别为a[i]dp[i-1]+a[i]
  • 所以转移方程为 dp[i]=max(a[i],dp[i-1]+a[i])dp[i]=max(0,dp[i-1])+a[i]

(3)对数组序列进行 前后缀分解,利用g[i]记录所有从1 ~ i中的最大子段和,h[i]记录所有从i ~ n中的最大子段和。
(4)枚举i的所有取值,两个连续子段的最大和即为g[i]+h[i+1]的最大值。

2、时间复杂度

时间复杂度为O(n)

3、代码详解

#include <iostream>
#include <algorithm>
using namespace std;
const int N=50010,INF=1e9;
int a[N],h[N],g[N],dp[N];
int T,n;
int main(){cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];dp[0]=g[0]=-INF;     //非法状态设置为负无穷//正着求一遍单段连续子段和for(int i=1;i<=n;i++){dp[i]=max(dp[i-1],0)+a[i]; //单段连续子段和的转移方程 g[i]=max(g[i-1],dp[i]);   //g[i]存储前1~i中子段和的最大值,如果1~i中的子段和最大值dp[i]比1~i-1中连续子段和最大值g[i-1]大,则g[i]=dp[i],否则g[i]=g[i-1]}dp[n+1]=h[n+1]=-INF; //非法状态设置为负无穷//倒着求一遍单段子连续段和for(int i=n;i>=1;i--){dp[i]=max(dp[i+1],0)+a[i];    //单段连续子段和的转移方程h[i]=max(h[i+1],dp[i]);   //h[i]存储i+1~n中连续子段和的最大值,类似g[]  }int ans=-INF;    //两段子段和的最大值可能是负数,所以将ans初始化为负无穷//遍历i的取值,找到两段连续子段和的最大值for(int i=1;i<=n;i++) ans=max(ans,g[i]+h[i+1]);cout<<ans<<endl;}return 0;
}

三、知识风暴

线性DP

http://www.zhongyajixie.com/news/15336.html

相关文章:

  • 网络策划岗位要求seo宣传
  • 东莞做网站哪里好市场营销推广策划
  • 如何做攻击类型网站如何建立免费公司网站
  • 日出东方网站建设资源猫
  • 网站建设报价书西安网站建设
  • 做网站线稿软件有哪些免费大数据分析网站
  • 做网站开发实习生怎么样长沙网络推广外包
  • 公司名字大全集免费泰州百度seo公司
  • 怎么做优化网站排名网站营销软文
  • 代练中介网站有得做吗seo服务运用什么技术
  • 做设计的地图网站展示型网站有哪些
  • 做体力活的网站推广如何做网上引流
  • 设计师常用网站优化大师app下载安装
  • 江苏优质网站制作公司网站优化人员通常会将目标关键词放在网站首页中的
  • 服装设计找图网站网站seo在线诊断
  • 网站建设 政府百度人工客服在线咨询
  • 用jsp实现网站开发实例谷歌浏览器安卓下载
  • 广东深圳网站建设方便app运营推广策划方案
  • 河北保定建设集团招聘信息网站辽宁好的百度seo公司
  • 武汉网站建设企业百度识图扫一扫入口
  • wordpress主题太大徐州seo外包
  • 免费建个人网站uc推广登录入口
  • 网站开发公司薪酬绩效关键词快速排名怎么做
  • 西安网站工作室百度登录页
  • wordpress 仿新浪微博网页优化建议
  • 青岛做网站公司排名百度关键词优化排名技巧
  • 外贸英文网站建设价格营销网址
  • 永兴房产网站东莞发布最新通告
  • 宁夏网站设计联系电话北京关键词seo
  • 做体育直播网站seo网站排名优化快速排