作者citronrisky (瑞士基)
看板Inference
标题Re: [问题] Maximum problem
时间Thu Nov 18 05:18:16 2004
※ 引述《Redsuns (ZZZzzz...)》之铭言：
: 1. 基本题
: 假设有一数列 {X1,X2,X3,X4,.....Xn}
: 请找出一演算法能够找出一连续的子数列,使他们的和为最大值
: 例: {2,-4,2,5,-2,3,4,-5,3,1} 则其子数列{2,5,-2,3,4}有最大的和
目前想到的方法:
step1
把头尾的负数去除掉(最大和的数列两端必不含负数)
ex:{-3,-4,2,5,-2,3,4,-5,3,1}
--> {2,5,-2,3,4,-5,3,1}
step2
把连续的负数或正数相加
(这时首末项是正数, 共有奇数项, 正负间隔出现)
ex:{2,5,-2,3,4,-5,3,1}
--> {7,-2, 7,-5, 4}
step3
比较首尾两项, 取小者, 将之与相邻的负数相加
如果小於零就把它从数列中移除,
如果大於零把它跟旁边的正数(即第三项或倒数第三项)相加
重复step3
ex:{7,-2,7,-5,4}
-->min(7,4)=4
-->{7,-2,7,-1}
^^舍去
-->{7,-2,7}
-->{5,7} (首末二项相等时,取首项或末项没有关系)
-->{12}
加到最後的答案应该就是那个最大值了
只要在过程中纪录头尾两项相对原始的数列是第几项即可
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 211.75.239.100
※ 编辑: citronrisky 来自: 211.75.239.100 (11/18 15:05)
※ 编辑: citronrisky 来自: 211.75.239.100 (11/18 15:11)