的确可以 model 为 isotonic regression, 并且可以 model 成一个 min-cost flow on a series-parallel graph.
然后就能 O(n log n)获得解法了.
算是这里面问题的简化版本.
http://chaoxuprime.com/posts/2015-01-27-bounded-regression-on-data-streams.html

@cbbxxt 感谢回复. 是的我对东西的了解还是以前的情况.
我发帖的时候由于自己当时 resume 做的不好, 被各各公司拒.
现在情况乐观了许多.

@chenzhihuai233 好玩, 以前并不知道你们组的存在. 我 3 月之后会在大陆呆到 7 月左右, 到时候如果去北京会 visit 一下.

@aphorism 竟然有人看过我这问题 233. 我在 cstheory 上还算 active. 现在 researcher 没有几年前多了, 好问题也少了.

@ruosongwang 你的未来应该很棒. 我做研究只是兴趣使然(还是蛮不喜欢写 paper 的). 所以决定不呆学术界了.

@Sweden 抱歉看太快. 有意思原来有这个, 第一次了解到.

@mickeyandkaka 感谢, 我在参考一堆中文简历, 先弄个像样的中文简历出来. 现在的简历是我申请教职 /postdoc 的时候稍微改一改得到的.

@AntiGameZ 并没有去做任何实习. 因为把做研究看的太重了. 几乎一半的 paper 都是在暑期想出来的.
刷题的话, 面试题类型的算法题是可以做的. 但做算法研究习惯是用更大的锤子, 这方面和数学家差不多. 所以还是要练练手. 美国 ACM 的确很水, 我们并不重视. 我们队伍一年训练大概 25 小时左右. Greater NY Region 那一年拿 No.2 都进不了 WF, 因为被哥伦比亚全中国人研究生队虐了(可见中国队实力之强).

@233 我在翻花书. 应该会试图把自己包装为一个 AI 人.

@withlqs 世界上又不缺我一个搞理论的人, 我已经带来了一些有用的东西了, 自己的幸福还蛮重要的. 毕业的话, 4 篇 SODA 完全足够了. 我应该把我的 2 篇 SODA 文+ESA+APPROX 的文章装订起来. 剩下 2 个 SODA 一个是我纯粹有兴趣做的, 另一个是和我前老板做的.

@roychan 不找教职. 我申 postdoc 只要是研究方向稍微近一点的 subfield 都能拿到. 但 postdoc 之后我的期望也是 (美国综排+计算机排名)>=100 的学校. 而我想这样的学校做教职没太大意义. 学生帮不了自己, 系里也没什么人做和自己差不多的东西, 最后是孤零零的一个人做研究. 除非早早就想要这样的生活, 这并不是很好的体验.

@Sweden 我想提一下做理论弄青千不容易. 我并不知道中国任何一个做理论 CS 的青千, 其中不乏一些在美国都能进 top 学校当教职的人. 因为和计算机系几乎任何其他方向比, 理论发 paper 的速度慢, 引用低, 名字排序也与众不同(姓氏序), 最后的最后, 我们和业界没有什么关系. 只有一次见有公司来 SODA 招聘, 还是高盛, 看起来主要是对我们数学能力有兴趣.
顶会都没几个人听过. 大陆没有几个学校的人能发那些会议, 像 2011 年开始直到 2018, 平均每年大陆 SODA 只能进 4 篇.
对于更广的工科来说, 计算机系人士不重视期刊. 而我去某大陆理工类 top 10 学校时, 被告知工院还是需要我有高质量的期刊文献的, 不然很难 argue 为什么要聘请我. 当然如果我早早打定去中国做教职, 那么我这 5 年会用其他的方法来优化自己的简历.
国内可以评定理论能力的人屈指可数. 这个可以看这里面的答案.
https://www.zhihu.com/question/43648215/answer/99167727
虽然感觉这超不公平, 但也可以理解. 毕竟大实话是: 理论人做的东西大多没啥用.
当然, 我是觉得再过个 10 年中国的理论 CS 也会发展壮大起来.

@mumuy 因为我们实际上解决的并不是同一个问题. 你可以看看整个文章.

@mumuy 我很高兴也有人想过这个问题. 但你有些评论并不适用于我们领域.

"感觉写成论文不合适了"
写成论文是否合适这个应该是学术界内的人评判.

"没有具体阐明怎么实现"
做理论的关心的是算法的理论复杂度. 我们并不关心是否真的写成一个程序. 如果有程序员写出来那是极好的. 但那不是我们的工作.

"而且我的程序处理的问题更复杂。"
我不知道你有没有看整个文章. 我们解决的不是同一个问题, 我们解决的是一个抽象的问题.
我在社交网络上所给的例子都是简单易懂的简化版, 所有词语都是相同权值的.
每个词语可以有不同权值, 我们要找的是最短的路径. 而且我的算法是适用于 sudanese pattern 的, 并没有专门对应中文亲属关系.
但是这都不是为什么我们发 paper. 重要的来自于我们证明了算法的复杂度和正确性(而正确性本身需要定义问题是什么).

"关键是，我的算法去年就开源了………"
这是我的疏忽, 没有发现你的这个程序. 等 IPL 那边 review 过后, 会在 introduction 的提到你的 library. 因为你超越了我们说的现有的两个 benchmark 的弱点(三姑六婆和小米内置计算器, 其实蛮奇怪的因为你提到内置用的就是你的系统).
但是, 你的程序不能解决我们要解决的问题.

@Xs0ul
1. 最差.
2. 这个算法就是传统的算法啊. 里面求最短满足一个 context-free language 的 path 就是动规.