＋设为首页 ＋添加到收藏夹
问题原型:给定一个一维向量,向量的值为正数或者负数,我们假定没有0(有0也没所谓,只是没什么意义),问哪一段向量的值与为最大? array arr[0...n] 存在 sum(arr[i]...arr[j]) is max!其中i,j属于[0,n].
【程序编程相关:[原创] 敏捷软件开发管理实践 (二) 】1.我尝试解决该问题的方法: 【推荐阅读:限制输入时候只能是英文或数字】
【扩展信息:游戏交互设计顶尖大师Chris Craw】 首先,引进两个数据结构: a.struct meta{ //记录可操作的某个元素 int val; //从这个位置到下一个meta的startpos之间的原向量的值之与 int startpos; //该值对应的原向量段的起始位置. }; b.struct maxrec{ //记录某个可能成为最大值的位置与值信息. int startpos; int endpos; int val; }; c.采用栈或队列的工作方式 d.采用预先格式化的数据信息:+ - + - + -......+ 即,使得可操作的数据信息成正负交替出现的 形式,这样有利于我们对数据的判断.当然第一个数据或者最后一个数据如果是负数的话,肯定是我们 舍弃的对象,这样最后出现的结果将是两端都是正数,格式化的过程就是把相连续的同号数累加在一 起,最终使得出现上面 的交替现象. 2.操作过程: 我们假设一次连续出现的三个值为o,p,q.其中o,q为正数,p为对应的负数的绝对值(相反数,因为一定是负数).对于o,p,q的不同大小关系可以列出下列情况,采用相对应的处理方式:
a.o<p<q 或 o<q<p :留下q,舍弃o,p.即最大的值一定从q开始.进行下面的重复计算 b.p<o<q 或 p<q<o :a+b+c作为一个整体成为一个meta进入下一个重复计算.即因为p是最小的,故他 们之与肯定比当中的任何一个正数都大,故如此处理. c.q<o<p :保存一个可能的最大值,那就是o.然后从q开始进行下面的计算,从q开始以后有 可能出现更大的最大值.但他们已不可能捆在一起,因为o+p<0,对q以后的数据不利,故如此处理,以后 得到更大的值时对最大值进行更新即可. d.q<p<o :同样o可能成为最大值,保存这个最大值,并且把o+p+q作为一个新的meta,进入 下一次的计算,之所以让o+p+q进入,是因为o+p>0,他对q来说是有利的,因此这样处理. 上面的四种情况可以总结成三种情况: ... 下一页