- Explaining the Stock Market
Mark Stockle has taken interest in analyzing the stock market. Recently, he has focused on a particular company’s stock. He observes the price of this stock over a period of N days. Then, he stares at these numbers for a long time and tries to identify the patterns and trends in the price. For example, he might notice that near the beginning of the N days, the price was decreasing, but then it steadily rising later. Or he might notice that generally the price was going up with the occasional daily dip. However, he was unable to come up with any rigorous or general approach for analyzing the stock.
One day, his friend suggested the following strategy: he ought to break up the problem of explaining N days of prices into smaller manageable subproblems. In particular, he would divide up the N days into K sets, and explain each set using a single hypothesis. Note that the days in a set do not have to be contiguous.
In his machine learning class, Mark learned the power of Occam’s Razor, which was that simple hypotheses that explain the data tend to generalize better on future data. It was so important for him to have simple hypotheses that he only allowed two types of hypotheses: that the prices of the stock on the days in a set would not increase or not decrease over time. Of course, there must be at least two days per set, since it does not make sense to explain the stock price of one day by itself. Lastly, the most important method to impose simplicity was to have as few hypotheses as possible, i.e. minimize K.
The first line contains N (1 ≤ N ≤ 30), the number of days for which Mark has collected stock prices. The next N lines contain N integers in the range [0, 100], one on each line. These integers represent the stock prices over N days.
On a single line, output K, the minimum number of hypotheses needed to explain the stock data. If it is impossible to explain the data using K hypotheses as described above, simply output 0.
- 博客 在中国程序员是青春饭吗？
- 博客 程序员请照顾好自己，周末病魔差点一套带走我。
- 博客 技术大佬：我去，你写的 switch 语句也太老土了吧
- 博客 和黑客斗争的 6 天！
- 博客 上班一个月，后悔当初着急入职的选择了
- 博客 女程序员，为什么比男程序员少？？？
- 博客 总结了 150 余个神奇网站，你不来瞅瞅吗？
- 博客 副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？
- 博客 如果你是老板，你会不会踢了这样的员工？
- 博客 我入职阿里后，才知道原来简历这么写
- 博客 外包程序员的幸福生活
- 博客 优雅的替换if-else语句
- 博客 深入剖析Springboot启动原理的底层源码，再也不怕面试官问了！
- 博客 离职半年了，老东家又发 offer，回不回？
- 博客 2020阿里全球数学大赛：3万名高手、4道题、2天2夜未交卷
- 博客 男生更看重女生的身材脸蛋，还是思想？
- 博客 为什么程序员做外包会被瞧不起？
- 博客 当HR压你价，说你只值7K，你该怎么回答？
- 博客 面试：第十六章：Java中级开发（16k）
- 博客 面试阿里p7，被按在地上摩擦，鬼知道我经历了什么？
- 博客 你期望月薪4万，出门右拐，不送，这几个点，你也就是个初级的水平
- 博客 面试了一个 31 岁程序员，让我有所触动，30岁以上的程序员该何去何从？
- 博客 大三实习生，字节跳动面经分享，已拿Offer
- 博客 程序员垃圾简历长什么样？
- 博客 《Oracle Java SE编程自学与面试指南》最佳学习路线图2020年最新版（进大厂必备）
- 博客 《Oracle Java SE编程自学与面试指南》最佳学习路线图（2020最新版）
- 博客 字节跳动面试官竟然问了我JDBC？
- 博客 面试官：你连SSO都不懂，就别来面试了
- 博客 终于，月薪过5万了！
- 博客 自从喜欢上了B站这12个UP主，我越来越觉得自己是个废柴了！