动态规划最大子序列.doc_第1页
动态规划最大子序列.doc_第2页
动态规划最大子序列.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1760: 最大数字子串Time Limit: 1500 ms Memory Limit: 10000 kB Judge type: Multi-casesTotal Submit : 1215(245 users)Accepted Submit : 397(209 users)Page View : 6115 Font Style: Aa Aa Aa 输入n(1=n0，如果后边是正数的话，完全可以加上这3个数（比如后边的5）-1 2 8 5 10 ？相同处理： -1 2 8 5 10 3 17 12？后面是-15，加上12（前面的子串能形成的最大和）也小于0，所以此处应该断开了！记录-15！最后-1 2 8 5 10 3 17 12 -15 1 8 4 13v 输入数组ai,用数组si记录最后一个数为ai时的最大子串和v 状态转移方程为v si=max(si-1+ai,ai);1=in-1v 初始条件s0=a0v 然后si中最大元素即为所求。AC代码：v #includev int a, s;v int main()v v int i,n,num;v while(scanf(%d,&n)v scanf(%d,&s);v num=s;v for(i=1;in;i+)v scanf(%d,&a);v if(s0)v s=a;v elsev s+=a;v if(nums) num=s;v v printf(%dn,num);v v return 0;v MLE代码：v #includev int a2000000,s2000000;v int main()v v int i,n,num; /num记录最大值v while(scanf(%d,&n)v for(i=0;in;i+)v scanf(%d,&ai);v num=s0=a0;v for(i=1;in;i+)v if(si-10)v si=ai;v elsev si=si-1+ai;v for(i=1;in;i+)v if(num
人人文库> 全部分类> 应用文书 > 工作计划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论