O(n)时间求一个数组里具有最大和的连续子集

有一个数组A={a1,a2,...,an}，求一个连续的子段的最大和，即ai,a_i+1, ... a_j-1,aj的和是A中最大的连续子段。

先给个大牛的贪心法：(为什么我觉得更像DP？）
ret=a[0],t=0;
for(i=1; i<n; i++){
    if(t<0) t=0;
    t+=a[i];
    if(t>ret) ret=t;
}
return ret; 

思路是：枚举以i为结尾的最大子段和

另外一个O(n)的算法是：
开另外一个数组s,s[i] = sum( a[0] ... a[i] )
由于s[j] - s[i] = sum (a[i+1] .. a[j] )
因此要maximize这个sum
则必须找一个最大的s[j]与一个最小的s[i]来maximize s[j]-s[i]
一个特例是，最小的s[i]初始为0，因为s[j]-s[i]不能表示到a[0]开始这个范围。
因此最小的s[i]必须为负数，否则必须为0

[转载]关于次贷危机的段子：卖猪记（秋叶瞎编）

阅读提示：猪是现金，伟哥是房子。

       一男赶集卖猪，天黑遇雨，二十头猪未卖成，到一农家借宿。
　　少妇说：家里只一人不便。
　　男：求你了大妹子，给猪一头。
　　女：好吧，但家只有一床。
　　男：我也到床上睡，再给猪一头。
　　女：同意。
　　半夜男与女商量，我到你上面睡，女不肯。
　　男：给猪两头。
　　女允，要求上去不能动。
　　少顷，男忍不住，央求动一下，女不肯。
　　男：动一下给猪两头。女同意。
　　男动了八次停下，女问为何不动？
　　男说猪没了。
　　女小声说：要不我给你猪……
　　天亮后，男吹着口哨赶30头（含少妇家的10头）猪赶集去了……

 

哈佛导师评论：要发现用户潜在需求，前期必须引导，培养用户需求，因此产生的投入是符合发展规律的。

       另一男得知此事，决意如法炮制，遂赶集卖猪，天黑遇雨，二十头猪未卖成，到一农家借宿
　　少妇说：家里只一人不便。
　　男：求你了大妹子，给猪一头
　　女：好吧，但家只有一床。
　　男：我也到床上睡，再给猪一头。
　　女：同意。
　　半夜男商女，我到你上面睡，女不肯。
　　男：给猪两头。
　　女允，要求上去不能动。
　　少顷，男忍不住，央求动一下，女不肯。
　　男：动一下给猪两头。女同意。
　　男动了七次停下，女问为何不动？
　　男说：完事了～～～女：......
　　天亮后，男低著头赶2头猪赶集去了......

哈佛导师评论：要结合企业自身规模进行谨慎投资，谨防资金链断裂问题

       又一男得知此事，决意如法炮制兼吸取教训，遂先去伟哥专卖店用一头猪去换一粒伟哥，然后带19头猪出发，事必，天亮后，男吹着口哨赶37头（含少妇家的18头）猪赶集去了……

哈佛导师评论：企业如果获得金融资本的帮助，自身经营能力将得到倍增。

       知道此法男多，伟哥供不应求，逐渐要2头猪换一粒伟哥，然后是3头猪换一粒伟哥，伟哥专卖店宣布伟哥限量供应，永远保值。

哈佛导师评论：这就是通货膨胀，但尽管购入伟哥，伟哥是永远保值品，从一头猪到N头猪换一个伟哥，你什么时候见过伟哥贬值？

越来越多的人听说了哈佛导师的评论，开始去囤积伟哥，并在市场上二手交易伟哥赚钱。

哈佛导师又评论：繁荣的二手交易市场是一手市场持续繁荣的保证。

越来越多的人想去炒做伟哥，很快伟哥价格涨到16个猪换一粒。

哈佛导师又评论：该男已经进入边际成本，除了拥有对自身能力的自信和未来良好愿望以外，实际现猪流已经为零。

有的男只有一头猪很早就换成伟哥，于是有人告诉他，你可以用你现在的这个伟哥去办猪抵押，当初你是一头猪买进，现在伟哥价值16头猪，你可以办至少8头猪的贷款，然后你可以用这些猪去买汽车等等好东西，这就可以把你伟哥增值部分去消费。

哈佛导师评论：良好的理财可以让个人实现财富自由。

换猪男越来越多，伟哥专卖店决定，推出一种借贷伟哥销售模式，即使你没有足够的现猪，只要你敢承诺到该女房中一夜，带16头猪回来，我就可以先把伟哥卖给你。例如如果你缺一头猪，就可以先欠一头，事成后补交猪款，这个方法大大促进了伟哥销售。

哈佛导师评论：这就是贷款，让企业可以根据未来的收益选择借支流动资金。扩展生产能力，这就是信用经济，信用经济是建立在良好信用和经济持续成长基础上的，只要大家都讲信用，伟哥就可以源源不断提供给大家使用。

 

伟哥专卖店尝到甜头，借贷胆子越来越大，后来在即使你一头猪都没有，只要你承诺可以到该女房中一夜，就可以先借，事成后补交猪款。

哈佛导师评论：这就是金融创新，让现在的人花未来的钱，反正等你老了未来的钱你也花不动。

消息一出，换猪男越来越多，有人找伟哥专卖店，这个项目太好了，我们把它变成优质基金，对外销售债卷，你们也就可以分享我的收益，如何？

结 果伟哥专卖店觉得甚好，于是该公司把换猪男分三类，一类是拿现猪换的，一类是一部分现猪贷的，一类是完全没有现猪借的，发行三种债卷。大家踊跃而上。纷纷 购买伟哥专卖店的债卷，伟哥专卖店生意太好，就把债卷销售外包给另外一家公司运作，该公司也一并大发其财，公司越做越大，甚至可以脱离实际伟哥销售情况来 发行，给自己和伟哥专卖店带来巨大的现金收益。

哈佛导师评论：这就是专业的人做专业的事，从实体经营到资本运作，经济进入了更高的层次。

为 了防止自己债卷未来有损失，该公司决定给它买上保险，这样债卷销售就更容易，因为一旦债卷出现问题，还可以获得保险公司的赔付，保险公司一计算，到目前为 止伟哥销售伟约率很低，毕竟做爱是刚性需求，必须满足，只要承诺可以接受保费，就可以获得一大笔收入，而违约风险很低。哇，所有的债卷如果出问题还有保险 公司负责理赔，债卷公司销售这下子太好了，保险公司也获得巨大平白无故的保险收入。

哈佛导师评论：这就是风险对冲，策略联盟，提高了企业的抗风险能力，也保护了消费者利益。

换猪男太多，排长队等待，该女无法承受，说老娘不干了，我搬家，一时间有无数拥有伟哥的欠猪男。

哈佛导师评论：这是个别现象，属于市场的正常波动，不会影响整个经济。

结 果该女迟迟不肯搬回。一部分欠猪男没有收入，只好宣布愿意低价交换伟哥，伟哥突然一下子从16个猪下滑到8个猪一粒也卖不掉，市场出现伟哥恐慌，原来伟哥 也可以暴跌，一些拥有伟哥的人赖帐，结果大量借贷到期无法返回现猪，伟哥专卖店晕了，不得不宣布有大量借贷者欠猪不还，属于信用违约。

哈佛导师评论：这是个人行为，大部分贷款是优质人群。

大量次级猪贷违约，那么对应他们的债卷也就一钱不值，承担销售的债卷公司一看一粒伟哥16头猪，这哪里还得起，宣布倒闭。

哈佛导师评论：这是次贷危机，不会影响整个金融贷款，

哈佛导师哪里晓得债卷公司还把债卷上了保险，保险公司一看，这哪里赔得起，于是也宣布要倒闭。

哈佛导师评论：这是金融危机，还不会影响整个实体经济。

大量的人破产，不敢消费，经过经济下滑，没有敢把猪借给别人，怕有去无回，市场越来越冷淡！

哈佛导师评论：全国人民都要出血的时刻到了，虽然那些卖伟哥的，卖债卷的，卖保险的在赚钱的时候发了财，现在搞出漏子了，如果我们不帮他们埋单，我们将来还是最大的受害者。

伟哥专卖局决定向全国人民借7000亿头猪拯救市场，市场依然故我，全国有猪者和无猪者都很愤怒，谁拿走了我们的猪？

哈佛导师评论：早就告诉你们，为什么不去监管？现在唯一的办法，就是找几个国外养猪户以负责任的大猪国形象来注猪，否则大家都要完蛋！
 

后文：据说该女已搬到中国定居，此外哈佛教授带的几个研究生也在中国淘金中。

 

想找我，请BAIDU或GOOGLE"秋叶"！
欢迎转载原创文章，请不要未授权用于商业用途，转载请留原始链接http://blog.vsharing.com/hopeful/！

总结：sth. about ramfs(ramdisk),loop device,tmpfs

ramfs,ramdisk,tmpfs,sysfs,devshm

sysfs是基于ramfs的？(wikipedia查ramfs自动重定向到sysfs)
ramdisk = ramfs?
tmpfs = ramfs?
devshm = tmpfs?

ramdisk
在linux里，可以使用内存（ram）模拟非易失性存储介质（如硬盘）。这就是所谓的ramdisk

loop device与loopback interface[3]
在linux里，loop设备是一个特殊的文件，它可以使得关联的文件作为一个虚拟的文件系统被读写。
比如在我的ubuntu里，默认有/dev/loop[0-7]共8个loop设备(这些文件通过/sbin/MAKEDEV脚本在启动时被创建)。
一个文件（如ISO）可以被挂载到一个目录上，以对其进行读写。
这个mount的过程实际上分为两步，
首先是进行文件与loop设备的关联，然后是挂载这个文件（或关联的loop设备）到目录上。
假设有一个img文件为example.img，要把它挂载到/home/you/dir上，则：

losetup /dev/loop0 example.img
mount /dev/loop0 /home/you/dir

但是也可以通过mount -o loop来一步完成：

mount -o loop example.img /home/you/dir

loop的作用一般有：

1. 挂载光盘ISO镜像（这个很常见）
2. 挂载其余镜像（如ramdisk，1.44' zip 镜像等，其实跟1是一个原理）
3. 挂载加密的文件进行读写（使得可以方便地进行加密文件读写）
   

loopback interface与loopback是两个概念，loopback interface是一个特殊的网络设备，俗称回环设备，指向本机自身。

loop device不够用了怎么办？
参见[4]


 参考文献：
[1]在Linux下使用RamDisk,http://blog.donews.com/stewchicken/articles/50640.aspx
[2]给你的Linux装备Ramdisk飚一下！,http://linuxdesktop.cn/2007/11/22/use-ramdisk-speed-up-your-linux/
[3]wikipedia loop device, http://en.wikipedia.org/wiki/Loop_device
[4]如何增加loop设备- - 自己搞定,http://ubuntu-fans.blogspot.com/2007/01/loop-1-etcmodutilslocaloptions-loop.html

CJKutf8 | pdflatex + eps 备忘

老是忘记怎么弄，写个备忘。

1.CJKutf8

\documentclass[a4paper,12pt]{article}
%不知道CJK和CJKutf8这两个package有什么区别
\usepackage{CJKutf8}
%hyperref好像有点问题：会使得copy出来的文字乱码。
%必须加入下面这条才行。
\usepackage[utf8]{hyperref}才行。
\title{Test}
\author{XIAO Zigang}

\begin{document}
\begin{CJK*}{UTF8}{gkai} % 对我的texlive，支持gbsn,gkai,bkai,bsmi
\maketitle
你好。
\end{CJK*}
\end{document}
%其中CJK*和CJK的区别在于：使用 * 的会自动删除两个汉字之间的空格以及换行。

2.pdflatex+eps
pdflatex很奇怪，支持很多图像偏偏不支持eps（但支持mps，用metapost生成的文件）
可以有两种方法解决这个问题：

1)使用latex -> dvipdf 生成（测试未通过！）
\usepackage[dvipdfm]{graphicx}

2)使用latex -> dvips -> pspdf生成
\usepackage[dvips]{graphicx}

3)使用pdflatex一步到位：通过使用pdftex驱动，用epstopdf转换eps为pdf
以及在pdflatex时加上--shell-escape选项。（最方便，也相当于先用epstopdf转换后直接include pdf文件）
\documentclass[a4paper,12pt]{article}
\usepackage[pdftex]{graphicx}
\usepackage{epstopdf}
\graphicspath{{/path/to/file}}  % 指定文件路径
\DeclareGraphicsRule{*}{eps}{*}{}  % 指定默认文件拓展名

\begin{document}
\begin{figure}[!ht]
\centering
\includegraphics{epsfile}  % 拓展名可带可不带
\end{figure}
\end{document}

上海海洋大学举行河蟹大赛

　　"328克！""420克！"……今天上午，第二届"丰收杯"全国河蟹大赛在上海海洋大学举行，所有参赛"选手"角逐的第一个环节是称重，雄蟹 体重在400克以上，雌蟹体重在300克以上，才有资格角逐"蟹王"、"蟹后"。据介绍，这届河蟹大赛的评选范围覆盖了长江流域的几十个河蟹品牌，旨在改 变河蟹市场较为混乱的局面，建立优质河蟹市场标准，让真正优质的河蟹产区大闸蟹找到市场。

　　上海海洋大学教授、农业部渔业科技入户首席专家王武是"丰收杯"河蟹大赛的发起人。他告诉记者，品蟹有一套"五星级"标准：一星肥，就是肉质饱 满；二星大，体格健硕；三星腥，这是大闸蟹特有的香气，蟹味浓郁；四星鲜，氨基酸越多，蟹越鲜；五星甜，富含甘氨酸的蟹肉口感清甜。本届比赛，采用了王教 授提出的"五星级"标准，在"大"的基础上，以"肥、腥、鲜、甜"为指标，评选出"金蟹奖"得主。

　　据了解，这届比赛还设立了"最佳口感奖"。该奖项的评比要经过视觉评定、嗅觉评定和味觉评定，惟有鳃白、腥味足、膏肥、肉微甜的蟹才有可能胜出。