Algorithm：

53: Maximum Subarray

对无后效性的理解：逻辑、条件和限制都要体现在某种设计的状态中，并且后续的状态都从前面已有状态中转换得出，不能依赖其他内容（如果依赖也要设计到状态中），已经有的状态不会被后面的状态所改变（后面的会用前面的但不会改变前面的），有时存在状态压缩技巧，看似会改变前面的状态，但是其实是因为前面的不需要复用，在用后用完即弃，只保留了最后状态，也不是改变前面的导致重新推导等情况。

这一题一开始尝试设计状态dp[n]是截止n的最大和，写出 dp[n] = max(dp[n-1], dp[n-1] + nums[n])，但是这是错误的，它把连续这一条件破坏了，结果是不连续的最大和。重新思考把 dp[n] 设计为截止并且包含n的最大和，这时方程如下，这里面表达出了 dp[n] 可能以当前点重新开始，当前点必须包括，连续性在这里体现。

if dp[n-1] > 0
 dp[n] = dp[n-1] + nums[n]
else
 dp[n] = nums[n]

152: Maximum Product Subarray

这题状态定义为包含nums[i]的最大（和最小）的数，这里有三个关键:

1. 是必须包含当前这个数
2. 并且可以不包含前面的数
3. 同时有两个状态最大值和最小值（而不是正负）

因为(1)如果可以不包含当前这个数，那就等同于nums[i-1]了，该状态就没有意义了，而(2)可以不包含前面的数则没有这个问题，体现了该dp定义的最大和最小概念，最后(3)dp中不需要考虑正负，是数学知识，不管正负只管大小就够用了。

空间优化的技巧总结，也叫表格复用，包括滚动数组（只用一行或两行）、滚动变量（一行也不用），不同题目用到的不同，注意不要提前覆盖还需要使用的状态。

120: Triangle

空间优化部分很典型，滚动数组的关键是识别不再需要的状态以及避免需要的状态被覆盖，因此倒着遍历就是这时的一个重要手段（两种都能用到但实施点不同），最后做完两种做法后可以看出一种更加简洁，即三角形从大的向小的方向转移，状态天然越来越少，更易处理。

Review：

Paper: The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform

京东图片搜索系统的工程论文，主要介绍了图片搜索系统设计和实时性能优化方面的内容，比较重点的有全量索引（按周进行近期图片补充）和增量索引（实时消息触发）流程、正排索引（图片编号到商品属性的索引）、倒排索引（图片特征到图片编号列表的索引列表 inverted list，图片提取出的特征用近邻算法属于哪一个类别或中心点）、三层架构（请求处理和结果排序返回、图片分区并行搜索、中间代理层）。

Tip：

如何避免文件名中的空格影响？

比如下面前者会因为空格失败，后者就可以避免

find . -type f | xargs md5
find . -type f -print0 | xargs -0 md5

因为xargs默认使用空格TAB换行分割记录，有空格会被当作两个文件，find的-print0可以让find在打印文件名后用NULL字符取代换行符分割，xargs的-0也是用NULL取代换行符分割，这样就不会被空格困扰。

其他需要注意的还有常用的循环处理中，也会出现该问题，这时最好使用 IFS 变量，替换分隔符。

SAVEIFS=$IFS
IFS=$(echo -en "\n\b")
for f in `ls .`
do
  echo $f
done
IFS=$SAVEIFS

Share：

如何独立思考

http://www.paulgraham.com/think.html

作者首先给出了关于一些独立思考的有趣现象，比如不同的工作对独立思考有着显著不同的需求、独立思考难以培养、容易高估自己的独立思考的倾向性等。

第二部分作者提出一些改善手段，比如减少了解常规的信念和思维、和有独立思想的人做朋友、和不同思想的人交流、阅读历史和将自己代入其中、培养质疑的态度、寻找错误观点的游戏、避免未经检查的想法等，还提到了有趣的一点，流行的知识（intellectual fashions）就像流行时装一样，要去寻找未经发现的观点。

最后从另一角度分析了独立思考的三个要素，对真相（truth）洁癖、抗拒被指手画脚（told what to think）、好奇心（curiosity），而这些更多是一种本能和习惯方面的内容。