动态规划 子串的最大和_第1页
动态规划 子串的最大和_第2页
动态规划 子串的最大和_第3页
动态规划 子串的最大和_第4页
全文预览已结束

下载本文档

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

文档简介

1、最大子段和：给定由n个整数组成的序列a1,a2,.an,求该序列子段和 的最大值！例如：(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2),最大子段和为 11 + (-4) +13=20针对最大子段和求解，本此贡献两种算法，一个是分治算法，一个是动 态规划。两种算法的时间复杂度不一样，分治算法是的时间复杂度为 T(n)=O(nlogn),动态规划的时间复杂度为T(n)=O(n).本次博客不做具体 分析，只提供java代码！ package com.liheng.algorithm;public class MaxSum (/* param args*功能：求最大子串

2、和*分别用分治法和动态规划两种方法，进行比较。更深入理解两种算 法的相同点和不同点*/final static int maxLen =100;public static void main(String args) (/ TODO Auto-generated method stubMaxSum ms = new MaxSum();int a = (-2,11,-4,13,-5,-2);int n= a.length;System.out.println(分治算法：+ ms.maxSumBin(n-1, a);System.out.println(动态规划算法：+ ms.MaxSumDin(

3、n-1, a);/*param nparam a分治算法求求最大字段和*/int maxSumBin(int n,int a) (return MaxSubSum(a, 0, n);int MaxSubSum(int a,int left,int right)(int sum=0;if(left=right) sum = aleft0?aleft:0;else(int center=(left+right)/2;分治递归，分别求左边和右边的最大值int leftSum二MaxSubSum(a, left, center);int rightSum = MaxSubSum(a, center+1, right);/*求两边的最大和，分别与两边的最大值进行比较*/int s1=0,lefts=0;for(int i=center;i=left;i-)(lefts+=ai;if(leftss1)s1=lefts;int s2=0,rights=0;for(int i=center+1;is2)s2=rights;sum=s1+s2;if(sumleftSum) sum=leftSum;if(sumrightSum) sum=rightSum;return sum;/*动态规划求最大字段和*/int MaxSumDin(int n,int a)(int sum=0

人人文库> 全部分类> 图纸下载 > 毕业设计

温馨提示

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

最新文档

评论

0/150

提交评论