最大子序列
挑战 5：最大子序列
子序列是一个列表中的一个或多个相邻元素的集合。例如，153是415368的一个子序列。子序列153的和为9。以下列表中任何子序列的最大和是多少？
-6 1 6 0 -3 -3 5 7 -9 3 -9 4 7 -5 1 6 -2 1 -5 7
每个数组中的 n 位置坐标 i , sub = sum(s[i:])数组形式追加到 sub数组
从左到右，找到两个sub的值相差最大的 2 个element的值
#初始化为 int
s = '-6 1 6 0 -3 -3 5 7 -9 3 -9 4 7 -5 1 6 -2 1 -5 7'
s = [int(i) for i in s.split(' ')]
def Maxseq(s):
seq = [sum(s[:i+1]) for i,e in enumerate(s)]
# 每个元素右边的所有数求和
mx = 0 #打擂台
for i,e in enumerate(seq[:-1]):
if max(seq[i+1:]) - e > mx:
mx = max(seq[i+1:]) - e
return mx
print(Maxseq(s))
14
有没有比较高效的算法？
遍历输入数组 s , sub = sum(s[:i])
sub < 0时，s[:i]一定不在最大子序列中，舍弃这一段,重新i+1开始遍历
s[i+1:]序列的最大值更替到 mx 变量
循环执行1，2步骤，直至数组结束
def Maxseq(s): #只输出最大序列的值
sub = mx = s[0]
for i in (s):
if sub < 0:
sub = i
else:
sub += i
mx = max([sub, mx])
return mx
print('solveOptimiz = ', Maxseq(s))
14
image.png
emma模拟兔子吃萝卜声音的魔笛。观察兔子听到魔笛后，都会奔向声音的方向，
不过，emma发现有的兔子并没有反应，她要找出有多少只耳聋的兔子？
传说中的魔笛
P = 魔笛手
O~ = 兔子向左走
~O = 兔子向右走
例子字符串格式给出魔笛 P 和兔子的位置，以及兔子奔跑的方向
1 OOOO P —>有0只的老鼠
P OOOO —>有1只聋哑老鼠
OOOOPOOO~ —>有2只聋鼠
# Your code here
def count_deaf_rats(town):
lft,rgt ='O~','~O'
l,r = [''.join(i.split(' ')) for i in town.split('P')]
ll = sum([1 for i in range(0,len(l)-1,2) if l[i:i+2]==lft])
rr = sum([1 for i in range(0,len(r)-1,2) if r[i:i+2]==rgt])
return ll + rr
原题来自codewars 难度为 6kyu 排名第一的写法如下
6 kyu The Deaf Rats of Hamelin
def count_deaf_rats(town):
return town.replace(' ', '')[::2].count('O')
Legend
P = The Pied Piper
O~ = Rat going left
~O = Rat going right
Example
ex1 OOOO P has 0 deaf rats
ex2 P O~ O~ ~O O~ has 1 deaf rat
ex3 OOOOPOOO~ has 2 deaf rats
索引 module -> mspace
记单词有一小诀窍，moon和mood一起比较着好记住
import mspace
mydict = file('dictionary.txt')
words = mspace.tokenizer(mydict)
index = mspace.VPTree(words, mspace.levenshtein)
你可以通过创建不带任何参数的索引，并在以后明确地调用构造，来推迟耗时的构造阶段。
index = mspace.VPTree()
index.construct(words, mspace.levenshtein)
请注意，索引的内容在每次调用构造时都会被驳回。索引是从头开始建立的，只有对象和距离函数作为参数传递。
执行范围搜索
在你建立了索引之后（如果索引很大的话，给自己弄点咖啡），你可以在其中搜索所有与给定其他对象的距离在任意范围内的对象。
index.range_search('WOOD', min_dist=0, max_dist=1)
['GOOD', 'WOOD', 'WOOL', 'MOOD']
['好', '木头', '羊毛', '心情']
在这种情况下，你收到了四个结果：你搜索的对象（显然它也在你的字典中）和另外两个对象 "GOOD "和 "WOOL"，这两个对象与你的查询对象的最大距离为1。结果列表是无序的，不包含关于其内容与查询对象的距离的信息。如果你需要这个，你必须手工计算它。
min_dist和max_dist都是可选参数，默认为零。因此，如果你不使用这两个参数，就会对与查询对象完全相等（由你的距离函数定义）的对象进行搜索。由于历史原因，以及最小距离为零、最大距离大于零的范围搜索非常普遍，所以有一个min_dist=0的搜索捷径。
min_dist=0:
index.search('WOOD', 1)
['GOOD', 'WOOD', 'WOOL', 'MOOD']
['好', '木头', '羊毛', '心情']
执行最近邻搜索
你可以执行的第二种类型的搜索是 "k-nearest-neighbour "搜索。它从索引中返回给定数量的与查询对象最接近的对象。搜索结果保证不会包含一个与查询对象的距离大于树中任何其他对象的距离的对象。
结果列表是由（对象，距离）图元组成，按距离升序排序。如果你没有指定要返回的最大匹配数，它默认为一个。
index.nn_search('WOOD')
[('WOOD', 0)]
index.nn_search('WOOD', 5)
[('WOOD', 0), ('WOOL', 1), ('GOOD', 1), ('MOOD', 1), ('FOOT', 2)]
请注意，该索引可能包含与查询对象'WOOD'距离为2的其他对象（例如'FOOL'）。它们只是被切断了，因为最多有五个对象被请求了。你对所选择的代表没有任何影响。
注意，你不能期望这个方法总是返回一个长度为num的列表，因为你可能要求的对象比当前索引中的对象多。
高级用法
为复杂的对象建立索引
如果你有 "复杂 "的对象，你只想通过一个特定的属性进行索引，你可以在levenshtein（或其他适用于该属性的函数）周围写一个简单的包装，从你的对象中提取这个属性，并返回它们的属性值之间的距离。这样，你就可以从索引中搜索和检索复杂的对象，同时只比较一个属性
import mspace
class Record(object):
def __init__(self, firstname, surname):
self._firstname, self._surname = firstname, surname
def firstnameLev(r1, r2):
return mspace.levenshtein(r1._firstname, r2._firstname)
index = mspace.VPTree(listOfRecords, firstnameLev)
rec = Record("Paul", "Brady")
index.search(rec, 2)
[<Record: 'Paula Bean'>, <Record: 'Raoul Perky'>, <Record: 'Paul Simon'>]
当然你也可以使用更高级的技术，比如写一个函数工厂，返回一个从你的对象中提取任意属性的函数，并对其应用一个度量函数。
def metric_using_attr(metric, attr):
def f(one, other, attr=attr):
attr1, attr2 = getattr(one, attr), getattr(other, attr)
return metric(attr1, attr2)
return f
metric = metric_using_attr(mspace.levenshtein, "_firstname")
metric( Record("Paul", "Brady"), Record("Paul", "Simon") )
0
0
(注意，本例中的内部函数f偏离了标准协议，接受了一个可选的第三个参数。这样做只是为了把名字attr拉到内层函数的名字空间中，以便在查找其相关值时节省一些时间。本模块中的任何索引结构都不会用两个以上的参数来调用它的距离函数，所以当你创建你的函数时，无论你把attr传递给metric_using_attr，当这个函数被一个索引调用时都会被使用。明白了
反向索引
当然，你可以使用类似的技术来避免完整的索引，而是创建一个只包含对你的数据（在数据库、文本文件、网络的某个地方等）的引用的索引。然后，你的距离函数将使用提供的值从你的数据源中获取要比较的对象。但是，我不能不强调这一点，你的距离函数的性能对于有效的索引和搜索是绝对关键的。因此，你应该确保你访问数据的方式是非常快的。
数据结构的选择
本模块目前有两种数据结构供你选择。虽然基础算法不同，但它们的搜索结果（给定相同的对象索引集、距离函数和最大距离）是完全相同的。如果你发现情况并非如此，请让我知道，因为这将是一个严重的错误。
能力
本模块中实现的算法有不同的能力，如下表所示。
VPTree BKTree
非离散公制X
插入 X
删除
第一行是关于索引使用的距离函数返回的值。BKTree没有准备好处理非离散的距离（例如浮点数），当它们发生时，很可能表现得非常糟糕。
另外两行描述了在索引构建完成后你可以对它们做什么。请注意，它们都不可能随着时间的推移而缩减。只有BKTrees能够有效地处理插入。
性能
[简而言之：你可能最好使用BKTrees，除非你需要一个非离散的度量。如有疑问，请测试这两个选项]。
很明显，这个模块的全部意义在于加快寻找彼此相似的对象的过程。而且，正如你所想象的，不同的算法在接触到一个特定的问题时表现不同。
这里有一个例子。我从Debian软件包wamerican-large中提取了文件american-english-large，并对其随机子集的索引和搜索做了一些时间测量。我使用的机器是一台1.1GHz的Pentium3，运行Python 2.4，来自Debian stable，启用了Psyco。请注意，以下的数字是完全不科学的。我展示它们只是为了给你一个预期的概念。对于严肃的基准测试，我应该使用timeit模块。尽管如此，这就是它。
BKTree VPTree
大小 每节点高度时间 每节点高度时间
5000 2.92 0.000584 11 7.40 0.001480 21
10000 6.32 0.000632 14 16.02 0.001602 22
15000 9.95 0.000663 14 28.35 0.001890 24
20000 13.70 0.000685 14 41.40 0.002070 24
25000 17.46 0.000699 15 50.63 0.002025 25
30000 21.81 0.000727 15 55.47 0.001849 25
35000 25.77 0.000736 16 64.43 0.001841 26
40000 29.40 0.000735 16 75.45 0.001886 26
45000 41.28 0.000917 16 96.36 0.002141 26
50000 37.62 0.000752 16 95.31 0.001906 28
该表显示了给定大小的数据集的构建时间（总时间和每个节点的秒数）。此外，你可以看到树的高度[3]。显然，BKT树的构建速度比VPT树快很多。它们都需要随着数据集的增加而增加每个节点的时间。这是预料之中的，因为在这两种情况下，构造复杂度都是O(n log(n))。
BK, size: 50,000 VP, size: 50,000
k 结果 时间 # 距离 时间 # 距离
0 0.89 0.0008 8.14 0.0019 17.28
1 4.07 0.1670 1583.77 0.2801 1933.64
2 38.10 1.1687 10353.31 1.4413 13845.67
3 304.57 2.5614 22202.28 3.0497 27514.51
4 1584.86 3.8727 32376.54 4.1518 36877.62
5 5317.03 4.4182 39616.04 4.9935 42720.38
该表显示了在树中进行搜索的运行时间（以秒为单位），所做的距离计算的数量以及误差容忍度不断增加的结果数量。所有的数值都是以100次随机搜索的平均值给出的（来自同一个文件，但不一定来自索引对象的集合）。正如你所看到的，搜索运行时间（与距离计算的数量紧密相连）对于较大的k值来说简直是爆炸性的增长。
正如你所看到的，大k值的长搜索运行时间实际上并没有对可用性造成很大的伤害，因为无论如何你只能得到小k值的可用结果数量。这当然是由于数据集的性质和这个例子中使用的距离函数。你的应用可能差别很大。
你还必须记住，我使用的字典几乎不包含重复的内容。如果你用一个真正的文档的单词作为你的数据集，你的树的节点会大大少于你文档中的单词数，因为你通常会经常重复很多单词。用我的毕业论文做了一个快速测试，发现在一个有14000个单词（包括LaTeX命令）的文档中只有4400个不同的单词。这使得搜索速度大大加快，因为相等的对象（由距离函数定义）只被评估一次。
[3] 如果你仔细观察，你可以看到，当数据集增长时，VPTree的高度并没有持续增长。造成这种现象的原因是，这个实现并没有很努力地去挑选一个好的有利位置，而这个有利位置是获得平衡性好的树的关键因素。因此，在某些情况下，选择的有利位置可能会导致树的高度超过严格意义上的需要。
优化潜力（或者说：为什么他妈的这么慢！？）
好吧，你已经尝试为你的小字典文件建立索引，并开始想知道为什么这个简单的任务要花上几分钟。这里有几个（可能的）原因。
对于目前实现的所有数据结构，索引需要O(n log(n))。所以，是的，索引对象的数量增加一倍必然会使你的索引运行时间增加一倍以上，对不起。
Python很慢。我已经写了一个与此非常相似的Java实现，它明显要快得多（大约是15到25倍，即使使用Psyco！）。但是java的实现会占用更多的内存，而且不幸的是，我不能以自由许可的方式发布它。
递归在Python中很慢。递归是创建和搜索树的最自然的方式，这段代码经常使用它。这个模块中的大部分递归是 "尾部递归"，但Python解释器不能将其优化为循环。
[注意：从第60版开始，在树中搜索和插入到BKTrees中都已经用循环代替递归重写了。不过性能的提高是相当小的]。
你的公制空间中的距离分布太密集了。这导致了数据结构在搜索时无法丢弃索引空间的大部分内容。在病态的情况下，你可能最终会出现类似于链接列表的数据结构。
你的距离函数是非离散的，也就是说，它返回的是浮点数。这方面的支持程度取决于使用中的索引结构。
你的度量函数是非常昂贵的。记住，这个函数在索引过程中必须经常被调用。你可以使用这个模块的属性dist_ctr来了解一下这样做的频率。在每次调用你的距离函数时，它都会被递增1，否则就不会被使用。
你正在搜索非相似的对象。例如，如果你有一个平均长度为6个字符的字符串索引，并且你正在不断地搜索最大距离为3或更多的字符串，不要指望搜索会比完整搜索空间的线性测试快得多。它甚至可能更慢。
可能的解决方案包括。
用C语言重写。由于我懒得学习C语言，所以必须由其他人来做这件事。
使用Pyrex或Psyco。用Psyco进行的快速测试表明，索引的速度大约是原来的3-4倍。这就像在你的程序中做一个 import psyco; psyco.full() 一样简单。请阅读Psyco的手册了解调整选项。
[注意：从第46版开始，在加载模块时，会尝试为levenshtein和树类导入并启用Psyco。如果没有成功，你会在stderr上得到一个性能警告，但一切都会继续完美地工作。］
用于静态数据集的pickle树。使用Python的标准pickle模块对索引进行腌制和解除腌制是相当快的。但是要注意，一个腌制的索引要比你的普通数据多出很多空间。
使用循环重写树的构造和搜索。我不确定这是否会更快，但它可能会比目前的方法占用更少的内存，并解决Python的递归限制问题。不过，我担心代码的可读性会受到影响。目前的实现方式与算法的原始描述相当接近。
[注：部分完成，见上文]。
优化使用中的距离函数。因为我不知道你的距离函数，所以我不能帮你解决这个问题。
至于levenshtein：本模块实现的算法是经典的动态编程变体，时间复杂度为O(|n||m|)（空间复杂度为O(min(|n|,|m|))）。其他Levenshtein的算法试图不计算整个矩阵，而只计算矩阵对角线附近严格需要的数值。通过这样做，经典动态编程算法的平均O(|n||m|)可以改进为类似O(k*|n|)。虽然这种方法在现实中能节省多少挂钟时间并不明显，但实际上可能会快很多，因为k通常只是输入字符串长度的一小部分。
如果你仔细看看这些算法，你可能会意识到，通过使用一种实际上并不计算两个字符串之间距离的算法，而只是回答两个字符串的距离是否小于或等于指定的最大距离的算法，可以加快搜索速度。这可以在O(k^2)中完成，并且应该可以明显提高搜索性能。
如果你对这些优化感兴趣，我建议你阅读Gonzalo Navarro的优秀调查报告《近似字符串匹配指南》，你可以从Citeseer获得。
目前，这个模块总是使用相同的函数进行搜索和索引。如果你想测试你自己的实现，你必须在索引和搜索之前替换你的索引对象的_func属性。
