文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > DP:最大连续子段和 到最优子矩阵
侵权投诉

DP:最大连续子段和 到最优子矩阵

NOIP必备

数列的连续最大和,顾名思义,就是在一个长度为n的数列{An}中,求i,j(1<=i<=j<=n),使得数列{An}中,第i个元素到第j个元素之间,所有元素的和最大。

var

a:array[1..1000] of integer;

best,sum,n,i:integer;

begin

ReadLn(n);

for i:=1 to n do Read(a[i]);

sum:=0; best:=0;

for i:=1 to n do

if sum+a[i]>0 then

begin

Inc(sum,a[i]);

if sum>best then best:=sum;

end

else sum:=0;

WriteLn(best);

end.

时间复杂度o(n)

在这一遍扫描数组当中,从左到右记录当前子序列的和temp_sum,若这个和不断增加,那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数,那么当前子序列的和将会减小。此时temp_sum 将会小于max,当然MAX也就不更新。如果temp_sum降到0时,说明前面已经扫描的那一段就可以抛弃了,这时将temp_sum置为0。然后,temp_sum将从后面开始将这个子段进行分析,若有比当前max大的子段,继续更新max。这样一趟扫描结果也就出来了。 这个时间复杂度O(N)!

最大连续子段和的拓展1

在一个长度为n的数列{An}中,求m个连续子序列,使得这m个连续子序列的和最大,且m个子序列无公共元素。

解决类似的问题,我们可以利用“加一维”的思想利用动态规划来解决。

用ans[i,j]表示数列前j个元素中,i个无公共元素的子序列的最大和,且必须包含第j个元素,数组no存放数列元素,则状态转移方程为:

ans[i,j]=max{ans[i,j-1]+no[j],ans[i-1,k]+no[j]} (i-1<=k<=j-1) 时间复杂度为O(n^3) 程序代码:

for i:=1 to m do

for j:=i to n do

begin

ans[i,j]:=ans[i,j-1]+no[j];

for k:=i-1 to j-1 do if ans[i-1,k]+no[j]>ans[i,j] then ans[i,j]:=ans[i-1,k]+no[j];

end;

第1页

你可能喜欢

  • 最大子段问题
  • 最大弯矩
  • 矩阵论最大秩分解
  • 最大和最小
  • xp最大连接数
  • 最大字段

热门文档

相关文档

  • 从连续最大和到最优子矩阵

    思考一下最优子矩阵和连续最大和的异同: 1、 所求的和都具有连续性; 2、 ... 子矩阵约束下矩阵反问题... 53页 免费 DP:最大连续子段和 到最... 9页...

  • 最大字段问题-含最大子矩阵和m子段和

    j1 i2 j2 最大子矩阵和问题的最优值为 1?maxm s(i1, i 2, j1, j...若干个连续的条,就是一个子矩阵了,这样 问题就轻易地转化为一维最大子段和...

  • 求最大子矩阵的两种思路

    从连续最大和到最优子矩... 14页 免费 最大子序列和最大子矩阵 3页 ...求最大子矩阵的两种思路长沙市雅礼中学 贺一骏 编者: 编者:求最大子矩阵问题...

  • 动态规划 最长子串与最大子矩阵问题

    动态规划 最长子串与最大子矩阵问题_计算机软件及应用_IT/计算机_专业资料。... acm中dp问题简单入门讲解... 32页 免费 poj1050动态规划求最大矩... 3页...

  • DP优化

    于是果断裸敲了一个自己的 ST: 矩阵快速幂: 矩阵快速幂: dp 转移方程中全是...相接的连续序列,总和最大 分析解结构: 满足子问题最优原理,搞起 i 段和 从...

  • DP动态规划ACM课件

    ? 此最优化问题不满足最优子结构,所以不适合用DP。 ? 但如果我们增加状态的...最大的值 } return sum; } 引申问题: 最大子矩阵和问题 最大m段子段和...

  • DP

    运用DP解决问题的步骤 ? 找出问题的最优子结构,并判断是否具有子 问题重叠性。...引申问题: 最大子矩阵和问题 最大m段子段和问题 一维状态存储问题 ? 硬币问题...

  • 05 递归与递推 最优子结构问题

    All rights reserved 二阶线性齐次递推的矩阵优化 ...从中选出连续的一段 使其和最大,问最大的和是...包含局部最优解 第一步:定义状态 定义dp[i]表示...

  • DP1

    基本概念状态 阶段 状态转移方程 决策 适合用DP解决的问题的性质最优子结构(...大子段和问题 最长递增子序列(LIS) ad hoc problems 二维状态存储问题矩阵连乘...

  • 最大子长方体问题

    若干子矩 阵,每个子矩阵都要转化成段,求出各个段的最大子段,要获得最大子矩阵,就得从这些最 大子段中比较求得,如果想获得最优解就必须对各个最大子段和的...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email